迪杰斯特拉(Dijkstra)算法

1.问题定义

给定一个带权有向图（或者无向图）G与源点v，求从源点v到G中其他顶点的最短路径，并限定各边上的权值大于0。

2.算法思路

图G={V,E} （1）初始时令 S={V},T=V-S={其余顶点}，T中顶点对应的距离值 若存在，dist(v0,vi)为弧上的权值 若不存在，dist(v0,vi)为∞ （2）从T中选取一个与S中顶点有关联边且权值最小的顶点u，加入到S中 ； （3）对其余T中顶点的距离值进行修改，若加进作中间顶点，从v0到vi的距离值缩短，则修改此距离值 （4）重复上述步骤(2)、(3)，直到S中包含所有顶点为止。

3.代码实现（C++）

#include 

using namespace std;

//定义图的顶点个数 
const int Node = 7;
//表示无穷大 
const int INF = 1000000000;

//输出单元最短路径
void Dispath(int arr[Node][Node], int dist[], int path[], int s[], int v){
	int i, j, k;
	//存放一条最短路径（逆向）及其顶点个数
	int apath[Node], d;					
	for (i = 0; i