dijkstra算法寻找最短路径 [英] dijkstra algorithm finding shortest path

问题描述

嗨我真的很困惑如何找到最短的路径这段代码显示最小距离但不是路径请解释我。

谢谢



这里是代码的链接。



http://www.geeksforgeeks.org/greedy-algorithms-set-7-dijkstras-algorithm-for-adjacency-list-representation/ [ ^ ]

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/[^]

推荐答案

这个页面上有很多文章，看看你是否找不到答案：

Dijstra算法 [ ^ ]

There are lots of articles on this very page, see if you cant find the answer here:
Dijstra algorithm[^]

嘿！



我在2天前写过dijgstra。

如果你想查看这段代码：

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.

:)

这篇关于dijkstra算法寻找最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！