Dijkstrův algoritmus – C / C++ – Fórum – Programujte.com

Dobrý den,

Našel by se někdo, kdo by mě pomohl s tímto programem ? (zadání je na začátku v poznámce). Pátral na netu a nějak to spichl. Pro mě, jako začátečníka, je to docela těžké zadání a topím se v tom :( Sprovoznil jsem menu, načítání souboru s maticí a jednoduchý zápis do souboru TXT (nevím jak zapsat výsledek jako pořadí uzlů, takže zapisuju jen nejkratší cestu).

Podle mě, to nepočítá správně, ale jsem rád, že jsem to aspon nějak rozchodil :D

Neměl by někdo čas to vyzkoušet ? (txt musí být ve stejné složce jako program a program mám uložený jako .cpp).  A jestli to pracuje správně, což si teda nemyslím, jak to zapíšu tak, aby zapsal i to pořadí uzlů ? 

Předem děkuji za ochotu.

Pro začátek jsem začal jen s malou maticí.

6
0 2 3 0 0 0
2 0 4 5 0 0 
3 4 0 1 2 6 
0 5 1 0 2 1
0 0 2 2 0 3
0 0 0 1 3 0

/*
zpracujte projekt pro vyhledání nejkratší cesty v grafu mezi 10 a více městy
1)menu programu
2)načtení dat z textového souboru do pole a výpis na obrazovku
3)určení počátečního a koncového uzlu
4)výpis nejkratší cesty
5)zápis cesty do textového souboru jako pořadí uzlů
6)konec
*/
#include<stdio.h>
#include<conio.h>
#include<process.h>
#include<string.h>
#include<math.h>
#define IN 99
#define N 6

int dijsktra(int hodnota[][N],int pocatek,int cil)
{
int vzdalenost[N],prev[N],vybrano[N]={0},i,m,min,start,d,j;
char cesta[N];

    for(i=1;i< N;i++)
    {
        vzdalenost[i] = IN;
        prev[i] = -1;
    }
start = pocatek;
vybrano[start]=1;
vzdalenost[start] = 0;
    while(vybrano[cil] ==0)
    {
        min = IN;
        m = 0;
        for(i=1;i< N;i++)
        {
            d = vzdalenost[start]+hodnota[start][i];
            if(d< vzdalenost[i]&&vybrano[i]==0)
            {
                vzdalenost[i] = d;
                prev[i] = start;
            }
            if(min>vzdalenost[i] && vybrano[i]==0)
            {
                min = vzdalenost[i];
                m = i;
            }
        }
        start = m;
        vybrano[start] = 1;
    }
    start = cil;
    j = 0;
    while(start != -1)
    {
       cesta[j++] = start+65;
        start = prev[start];
    }
    cesta[j]='\0';
    strrev(cesta);
    printf("%s", cesta);
}

main()
{

int hodnota[N][N],i,j,w,co;
int pocatek,cil,x,y;
int pocet,akce;
FILE *fd;

do
 {
    printf("\n\n******  MENU  *******\n\n");
    printf("\n\nZvol jednu z techto moznosti:\n\n");
    printf("1 - Nacteni dat ze souboru\n");
    printf("2 - Urceni pocatecniho a konceveho uzlu\n");
    printf("3 - Zapis cesty do textoveho souboru jako poradi uzlu\n");
    printf("0 - KONEC programu\n\n");
    printf ("povel:");
    scanf ("%d",&akce);
  
    switch (akce)
 {
     case 1:
    printf("Provadim akci 1\n\n");
 
    for(i=1;i<N;i++)
    for(j=1;j<N;j++)
    hodnota[i][j] = IN;
    
    if((fd=fopen("uzly.txt","r"))==NULL);
    
	fscanf(fd,"%d",&pocet);  
    printf(" %d\n",pocet);
    
    for(x=1;x<pocet;x++)
    {
        for(y=x+1;y<N;y++)
        { 
            fscanf(fd,"%d",&w);
            hodnota [x][y] = hodnota[y][x] = w;
            printf("[%d][%d] = [%d][%d]= %d\n",x,y,y,x,w);
        }
        printf("\n");
    }
    break;
      
	  case 2:
    printf("Provadim akci 2\n\n");
    printf("\nZadejte pocatecni uzel: ");
    scanf("%d", &pocatek);
    printf("\nzadejte cilovy uzel: ");
    scanf("%d", &cil);
    co = dijsktra(hodnota,pocatek,cil);
    printf("\nNejkratsi trasa je: %d",co);
    fclose(fd);		
	break;
		
	 case 3:
	 printf("Provadim akci 3\n\n");
	 fd=fopen("uzly1.txt","w");
	 fprintf(fd,"Nejkratsi trasa je: ""%ld",co);
	 fclose(fd);
	 break;	   
  
	default:
	printf("Chybny povel\n\n");	 	
  }  
 }
   while (akce!=0);
printf("Konec programu\n\n");
system("PAUSE");
}

#1 Michal
Takhle zběžným pohledem (pouze Dijkstra, menu a načítání vstupních dat jsem neřešil) mi připadá, že by to mělo, až na pár dost podstatných vad, fungovat. Není to sice zrovna nejefektivnější implementace Dijsktry, ale měla by být funkční. Ty podstatné vady jsou:

• zvětšete si výrazně hodnotu pro nekonečno,
• pole vybrano inicializujte v cyklu stejně jako pole vzdalenost a prev,
• v C se pole indexují od 0. Pokud máte for(i = 1; i < N; ++i), pak jste zapomněl projít první prvek a proiterujete pouze N - 1 prvků. Tahle chyba se vám vyskytuje všude včetně načítání vstupních dat.

Vzhledem k tomu, že v zadání máte "10 a více", tak výpis uzel + 65 nemůže fungovat. Místo charového pole si pro cestu udělejte intové pole a pomocí printf("%d") ji pak pozpátku vypište.

Z pohledu lajka, ktery nevi o 'Dijkstrův algoritmus' vubec nic, resim nejkratsi cestu tak, ze si ...
- z herni plochy vygeneruji seznam policek a jejich sousedu, pole S. s[0] = [0, null, 1, 8, null] (na sachovnici nahore nic, vpravo pole 1, dole pole 8, vlavo nic - smery jsou podle hodinovych rucicek)
- pak zjistim existenci bodu A a B v poli (v php je to isset($s[$a])), aby mi tam treba nekdo nezadal neexist bod
-
x = []
x[] = [a, null] // pridam prvni,
y = 0 // pridam vsechny sousedy prvniho policka
x[] = [s[x[y]][0], y]
x[] = [s[x[y]][2], y] //sx0-1,3 neexistuje, ty nepridam
y++ // pridam sousedy sousedu
x[] = [s[x[y]][0], y] atd
atd, dokud nenarazim na bod B. Pak mam na vyber, kdy program ukoncim a zpetne vratim seznam policek. Nebo pokracuji jeste pro vsechny sousedy a pak nahodne vybiram trasu.

Nikdy jsem to neresil z tabulky vzdalenosti. Tam je to asi podobne. Jenom navic musis scitat vzdalenost a kdyz narazis na bod B najit ze vsech poslednich dat tu nejkratsi.

#3 peter
Bohužel to tak nefunguje. Když se omezím pouze na šachovnici (což je méně obecné, než vyžaduje zadání), tak je potřeba si uvědomit, že nejkratší cesta nemusí nutně být také nejkratší na počet posunů na šachovnici (hran v grafu). Ve skutečnosti, pokud správně ohodnotíte hrany, vám nejkratší cesta může oběhnout několikrát šachovnici dokola nebo se různě kroutit apod. Takže pokud vámi popsaným algoritmem dosáhnete bodu B, v žádném případě nemáte jistotu, že jste našel nejkratší cestu.