4. Djikstra Algorithmus, Problem

Djikstra Algorithmus, Problem

  • W

    Ich hoffe ich habe das Thema im richtigen Unterforum gepostet

    Ich habe mit dem folgenden code ein Problem, und zwar habe ich ein mehrdimensionales Array in welchem meine möglichen Entfernungen der Punkte eingespeichert sind, das Programm welches ich geschrieben habe ist soweit schön und gut, nur wenn ich M als Endpunkt der Rute eingeben und als Start einen anderen Knoten als A, N, oder L wähle kommt bei mir immer die oo = "undendliche" entfernung heraus und er zeigt mir keine Route an

    edit: ich finde einfach nicht den Fehler, kann mir evtl wer helfen und sagen woran es liegt....

    #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
/* Anzahl an Knoten */
#define MAX_NODES 9
/* "unendlich" = groesste Integer-Zahl (limits.h) */
#define oo INT_MAX

/* Funktionsruempfe */
int readNode(int);
void printShortestPath(int);
void calcPath(int);
int minDistIndex(int);

/* globale Variablen */

/* calculatedDistance[i] : Länge des kürzesten Pfades zwischen Start und Knoten i */
int calculatedDistance[MAX_NODES];

/* predecessor[i] ist Vorgänger vom Knoten i im kürzesten Pfad */
int predecessor[MAX_NODES];

/* 2D-Matrix speichert die Entfernungen
* Die Reihenfolge ist willkürlich, muss aber mit der der Namen übereinstimmen (s.u.) !
*/
int distances[MAX_NODES][MAX_NODES] =
{
/* M A K DO H L N S KS */
{ 0, 80, oo, oo, oo, 430, 166, oo, oo }, /* M */
{ 80, 0, 521, oo, oo, oo, oo, 160, oo }, /* A */
{ oo, 521, 0, 95, oo, oo, oo, 369, oo }, /* K */
{ oo, oo, 95, 0, 213, oo, oo, oo, 167 }, /* DO */
{ oo, oo, oo, 213, 0, 262, oo, oo, 164 }, /* H */
{ 430, oo, oo, oo, 262, 0, 281, oo, oo }, /* L */
{ 166, oo, oo, oo, oo, 281, 0, 208, 310 }, /* N */
{ oo, 160, 369, oo, oo, oo, 208, 0, 355 }, /* S */
{ oo, oo, oo, 167, 164, oo, 310, 355, 0 }, /* KS */
};

// Namen der Staedte
char *names [] = {"M", "A", "K", "DO", "H", "L", "N", "S", "KS"};

int main() 
{
	int start = 0;
	int destination = 0;

	system("cls");
	printf("Start: ");
	start = readNode(0);
	printf("\nZiel: ");
	destination = readNode(1);
	calcPath(start);

	printf("\n Die Route lautet: ");
	printShortestPath(destination);
	printf("\n Die Entfernung beträgt: %i km", calculatedDistance[destination]);

	return 0;
}

/*
* Liest Start- bzw. Zielknoten ein
*
* @param isZiel 0 für Startknoten, 1 für Zielknoten
*/

int readNode(int isZiel)
{
	char* nodename = (char*)malloc(2*sizeof(char));
	while(1)
	{
		int i;
		scanf("%s", nodename);
		for(i=0;i<MAX_NODES;i++)
		{
			if(strcmp(nodename, names[i]) == 0)
			{
				return i;
			}
		}
		printf("\nUngültige Eingabe\n\nNeue Eingabe: ");
	}
}

/*
* Gibt den kürzesten Pfad (rekursiv) aus
*
* @param destination Ziel der Route
*
*/
void printShortestPath(int destination)
{
	printf("%s", names[destination]);
	if(predecessor[destination] != -1)
	{
		printf(" <- ");
		printShortestPath(predecessor[destination]);
	}
}

/*
* Berechnet die kürzesten Pfade vom Startknoten aus anhand des Algorithmus von Dijkstra.
*
* @param start Startknoten
*
*/
void calcPath(int start)
{
	int i;
	int z;
	int j;
	//Initialisierung des Algorithmus
	for(i=0;i<MAX_NODES;i++)
	{
		if(i!=start) 
		{
			calculatedDistance[i] = oo;
		}
		else
		{
			calculatedDistance[i] = 0;
		}
		predecessor[i] = -1;
	}

	//Eigentlicher Algorithmus
	for(z=0;z<MAX_NODES;z++)
	{
		i = minDistIndex(z);
		//printf("aktueller knoten: %i\n",i);
		for(j=0;j<MAX_NODES;j++)
		{
			//printf("versuche Expansion: %i\t%i\n", j, distances[i][j]);
			//IF nicht der knoten selbst, oo => knoten ist kein nachfolger, nicht da hin wo wir herkommen
			if(distances[i][j] != 0 && distances[i][j] != oo && predecessor[j] != i)
			{
				//printf("expandiere nachfolger: %i\n",i);
				int tempDist = calculatedDistance[i] + distances[i][j];
				//IF aktueller wert < gespeicherter knotenwert => aktualisiere
				if(calculatedDistance[j] > tempDist || calculatedDistance[j]==oo)
				{
					calculatedDistance[j] = tempDist;
					predecessor[j] = i;
					//printf("%i\t%i\t%i", i, j, predecessor[j]);
				}
			}
		}
	}

}

/*
* Findet den Knoten mit geringster berechneter Distanz
*
*@param aktuellerKnoten Der Knoten, der gerade untersucht wird
*/
int minDistIndex(int aktuellerKnoten)
{
	int i;
	int distTemp=oo;
	int nodeIndex=-1;
	for(i=aktuellerKnoten;i<MAX_NODES;i++)
	{
	if(calculatedDistance[i] < distTemp)
	{
		distTemp = calculatedDistance[i];
		nodeIndex = i;
	}
}
return nodeIndex;
}
    0
  • T

    Nein hast Du nicht. Ansi C wäre wohl korrekt.

    0
  • Administrator

    Und zur Problembehebung:
    Benutze einen/den Debugger und gehe Schritt für Schritt durch, dann erkennt man schnell, wo das genaue Problem liegt.

    Grüssli

    0
  • J

    Ich denke, das ist ein Fehler im Algorithmus. So wie es da steht, wirst Du Knoten 0 nur in der ersten Runde versuchen zu expandieren und danach nie wieder.

    0
  • W

    Jester schrieb:

    Ich denke, das ist ein Fehler im Algorithmus. So wie es da steht, wirst Du Knoten 0 nur in der ersten Runde versuchen zu expandieren und danach nie wieder.

    Also entweder bin ich da jetzt zu blöd, aber ich finde den Fehler da nicht bzw was müsste ich da umschreiben, sorry ich steh grad voll aufm schlauch...

    0
  • Administrator

    Hast du denn nun schon einmal den Debugger benutzt?

    Grüssli

    0
  • J

    Die Funktion minDistIndex liefert Dir für eine gegebene Zahl den Knoten mit dem kleinsten Abstand und index größer als die gegebene Zahl. Am Anfang ist z=0 und jeder Knoten kann gewählt werden. Die Variable z wird aber hochgezählt und dadurch werden ab dem nächsten Durchlauf nur noch Knoten mit Index >=1 betrachtet, genauer im i-ten Durchlauf Knoten mit Index >=i-1.

    Aber es sollte durchaus erlaubt Knoten 0 zu einem deutlich späteren Zeitpunkt noch zu expandieren.

    0
Anmelden zum Antworten