Dijkstra算法（单元点最短路径）

Dijkstra算法解决图中某特定点到其他点的最短路径。

迪杰斯塔拉（Dijkstra）算法思想：

按路径长度递增的次序产生最短路径的算法。设集合S存放已经找到最短路径的顶点,V为所有节点的集合，S的初始状态只包含源点V0，对Vi∈V-S。

假设从源点V0到Vi的有向边为最短路径，以后每求得一条最短路V0……Vk，就把Vk加入集合S里，并将路径V0……Vk,Vi与原来的假设比较，取路径较短者为最短路径。

重复上述过程，直到集合V中全部顶点加入集合S里。算法结束。

理解：

①对于集合S和集合V-S，每次迭代都把集合V-S中与源点V0距离最小的点Vk加入集合S，

②然后重新计算集合V-S中所有点与V0的最短距离

③如果所有点都已经加入S则结束，否则继续从①开始

/*************************************************************************
    > File Name: Dijkstra.cpp
    > Author: Shorey
    > Mail: shoreybupt@gmail.com
    > Created Time: 2015年04月24日 星期五 17时12分25秒
 ************************************************************************/
 
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<stack>
#define M 100
#define N 100
#define INT_MAX 10000
using namespace std;
typedef struct node
{
	int matrix[N][M];
	int n;
	int e;
}MGraph;
 
void DijkstraPath(MGraph g, int *dist, int *path, int v0)//v0表示源顶点
{
	bool *visited = new bool[g.n];
	for(int i=0; i<g.n; i++)              //初始化工作
	{
		if(g.matrix[v0][i]>0 && i!=v0)
		{
			dist[i] = g.matrix[v0][i];
			path[i] = v0;
		}
		else
		{
			dist[i] = INT_MAX;           //若i不与v0直接相邻，则权值为无穷大
			path[i] = -1;
		}
		visited[i] = false;
		path[v0] = v0;
		dist[v0] = 0;
	}
	visited[v0] = true;     //v0设为已经访问
 
	for(int i=1; i<g.n; i++) //循环n-1次，寻找把剩余结点加入的路径
	{
		int min = INT_MAX;
		int u;
		for(int j=0; j<g.n; j++)//寻找未被扩展的权值最小的顶点
		{
			if(visited[j]==false && dist[j]<min)
			{
				min = dist[j];
				u = j;
			}
		}
		visited[u] = true;//把上步找到的结点加入路径中
		for(int k=0; k<g.n; k++)//更新dist数组的值和路径的值
		{
			if(visited[k]==false && g.matrix[u][k]>0 && min+g.matrix[u][k]<dist[k])
			{
				dist[k] = min+g.matrix[u][k];
				path[k] = u;
			}
		}
	}
}
 
void showPath(int *path, int v, int v0)
{
	stack<int> s;
	int u = v;
	while(v!=v0)
	{
		s.push(v);
		v = path[v];
	}
	s.push(v);
	while(!s.empty())
	{
		printf("%d ",s.top());
		s.pop();
	}
}
int main()
{
	int n,e;
	while(scanf("%d%d",&n,&e) && e!=0)
	{
		MGraph g;
		int v0;
		int *dist = new int[n];
		int *path = new int[n];
		for(int i=0; i<N; i++)
			for(int j=0; j<M; j++)
				g.matrix[i][j] = 0;
		g.n = n;
		g.e = e;
		for(int i=0; i<e; i++)
		{
			int s,t,w;
			scanf("%d%d%d",&s,&t,&w);
			g.matrix[s][t] = w;
		}
		scanf("%d",&v0);
		DijkstraPath(g, dist, path, v0);
		for(int i=0; i<n; i++)
		{
			if(i!=v0)
			{
				showPath(path, i, v0);
				printf("%d\n",dist[i]);
			}
		}
	}
	return 0;
}