/* gcc -o dijkstra dijkstra.c -lm */ #include #include #include #define INF 99999.9 #define n 33 //Dimension des Gitters #define m 22 // #define s1 11 #define s2 3 //s1(y) und s2(x) sind koordinaten des Startpunktes (0 mit Bedenken, bei 20x20 Gitter ist 19 19 der letzte Punkt) #define e1 10 #define e2 14 //e1(y) und e2(x) sind koordinaten des Endpunktes struct Knoten{ float Entf; int Vorg[2]; char Art; //H = Hindernis , P= Punkt, S= Start, E= Ende , W= Wegpunkt (nach loesung) char Besucht; //J=Ja, N=Nein char Warte; //J= Ja, N=Nein int Koord[2]; }; void Initialisierung (); void Ausgabe (); void Dijkstra (); void Nachbarknoten (int XPos,int YPos); void minIndex (struct Knoten Gitt[][m], int index[]); void KuerzesterWeg (); int i; int j; int c=0; //Anzahl der Knoten in Warteschlange minus 1 struct Knoten Gitter[n][m]; int main(void){ Dijkstra(); return 0; } void Initialisierung(){ for (i=0 ; i=0){ minIndex(Gitter , index); x=index[0]; y=index[1]; Nachbarknoten (x,y); Ausgabe(); /*Verbesserung des Algorythmus nach Aufgabenstellung, bricht nun ab, sobald der Endpunkt erreicht wurde (restliche Wege sind alle länger oder gleichlang in besonderen Situationen) */ if(Gitter[x][y].Art == 'E'){ break; } /////// usleep(5000); } KuerzesterWeg(); } void Nachbarknoten (int XPos,int YPos) { float alternative; Gitter[XPos][YPos].Besucht = 'J'; Gitter[XPos][YPos].Warte ='N'; c=c-1; for (i=XPos-1 ; i<=XPos+1 ; i++) { for (j=YPos-1 ; j<=YPos+1 ; j++) { if (!(Gitter[i][j].Art == 'H')){ if ((i>=0 && j>=0) && (iXPos) && (j>YPos)) || ((i>XPos) && (jYPos))) || ((iXPos) && (j>YPos)) || ((i>XPos) && (jYPos))) || ((i

dijkstra Algorithm for Linux(Ubuntu)