Click here to Skip to main content
14,643,391 members
Rate this:
Please Sign up or sign in to vote.
See more:
hi i am really confuse how to find shortest path this code shows the minimum distance but not path kindly explain me.
thank you

here is link of the code.

http://www.geeksforgeeks.org/greedy-algorithms-set-7-dijkstras-algorithm-for-adjacency-list-representation/[^]
Posted
Rate this:
Please Sign up or sign in to vote.

Solution 1

There are lots of articles on this very page, see if you cant find the answer here:
Dijstra algorithm[^]
   
Rate this:
Please Sign up or sign in to vote.

Solution 2

Hey!

I wroted the dijgstra 2 days ago.
If you want look this code:

#include <cstdio>
#define MAXN 150
#define MAX_VALUE 10000
#define NO_PARENT (unsigned)(-1)
const unsigned S = 1;
const unsigned N = 10;

unsigned Matrix[MAXN][MAXN] =
{
	{0, 23, 0, 0, 0, 0, 0, 8, 0, 0},
	{23, 0, 0, 3, 0, 0, 34, 0, 0, 0},
	{0, 0, 0, 6, 0, 0, 0, 25, 0, 7},
	{0, 3, 6, 0, 0, 0, 0, 0, 0, 0},
	{0, 0, 0, 0, 0, 10, 0, 0, 0, 0},
	{0, 0, 0, 0, 10, 0, 0, 0, 0, 0},
	{0, 34, 0, 0, 0, 0, 0, 0, 0, 0},
	{8, 0, 25, 0, 0, 0, 0, 0, 0, 30},
	{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
	{0, 0, 7, 0, 0, 0, 0, 30, 0, 0},
};

char Tops[MAXN];
unsigned d[MAXN];
int pred[MAXN];

void Dijkstra(unsigned s)
{
	unsigned i;
	for(i = 0; i < N; i++)
	{
		if(Matrix[s][i] == 0)
		{
			d[i] = MAX_VALUE;
			pred[i] = NO_PARENT;
		}
		else
		{
			d[i] = Matrix[s][i];
			pred[i] = s;
		}
	}
	for(i = 0; i < N; i++)Tops[i] = 1;
	Tops[s] = 0;
	while(true)
	{
		unsigned j = NO_PARENT;
		unsigned di = MAX_VALUE;

		for(i = 0; i < N; i++)
		{
			if(Tops[i] && d[i] < di)
			{
				di = d[i];
				j = i;
			}
		}

		if(NO_PARENT == j)break;
		Tops[j] = 0;
		for(i = 0; i < N; i++)
		{
			if(Matrix[j][i] != 0 && Tops[i])
			{
				if(d[i] > d[j] + Matrix[j][i])
				{
					d[i] = d[j] + Matrix[j][i];
					pred[i] = j;
				}
			}
		}
	}
}

void printPath(unsigned s, unsigned j)
{
	if(pred[j] != s)printPath(s, pred[j]);
	printf(" %u", j + 1);
}

void printResult(unsigned s)
{
	unsigned i;
	for(i = 0; i < N; i++)
	{
		if(i != s)
		{
			if(d[i] == MAX_VALUE)
			{
				printf("NO PATH FROM TOP %u TO TOP %u\n", s + 1, i + 1);
			}
			else
			{
				printf("MINIMAL PATH FROM TOP %u TO TOP %u: %u", s + 1, i + 1, s + 1);
				printPath(s, i);
				printf(", PATH LEINTH: %u\n", d[i]);
			}
		}
	}
}

int main()
{
	Dijkstra(S - 1);
	printResult(S - 1);
	return 0;
}</cstdio>


I'd like I was helpful.

:)
   

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100