1.问题描述

? ? ? ? 对于有向带权图G=(V,E)，其中每条边的权值都是非负实数。给定V中的一个节点（称为源点），计算源点到其他各节点之间的最短路径，即单源最短路径。

2.问题分析

????????Dijkstra算法是解决单源最短路径问题的贪心算法。Dijkstra算法基本思路是先求出源点离当前节点最短的一条路径，然后根据当前最短路径末端点能够到达的点求出下一条离源点最近的路径，直到求出源点到其他各节点的最短路径。

3.算法设计

????????将节点集合V划分为两部分——集合S和V-S（节点总的集合减去已经确定最短路径的点的集合）。其中，集合S中的节点到源点的最短路径已经确定，集合S中的节点到源点的最短路径已经确定，集合V-S中节点的路径称为特殊路径，数组dist[]用于记录从源点到每个节点的最短特殊路径的长度。Dijkstra算法的贪心策略是选择最短的特殊路径长度dist[t]，将节点t添加到集合S中，同时借助节点t更新dist[]。一旦集合S包含了所有的节点，dist[]就是从源点到其他节点的最短路径长度。

具体步骤如下：

1）确定合适的数据结构。用邻接矩阵(二维数组G[][])存储图，用一维数组dist[i]记录从源点到节点i的最短路径长度，用一维数组p[i]记录最短路径上节点的直接前驱，例如p[2]=3，则2的前一个节点为3；

2）初始化。假设节点u为源点，令集合S={u}，对于集合V-S中的节点i，初始化dist[i]=G[u][i]。入股从源点u到节点有边相连，就初始化p[i]=u，否则初始化p[i]=-1；

3）找最小。根据贪心策略查找集合V-S中dist[]最小的节点t，t就是集合V-S中距离源点u最近的节点，将节点t添加到集合S中；

4）执行松弛操作。对于集合V-S中的所有节点j，检查是否可以借助节点t得到更短的路径。如果源点u经节点t到节点j的路径更短（即：dist[j]>dist[t]+G[t][j]），则更新dist[j]=dist[t]+G[t][j]（即执行松弛操作）并记录j的直接前驱为t（即p[j]=t）。

5）重复步骤3和4，直到集合V-S为空。由此可以得到源点u到其他各节点的最短路径长度，此位还可以通过前驱数组p[]逆向找到最短路径上经过的点。

4.C++程序

//program 2.5.0 dijkstra算法
#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
const int N = 1005;
const int INF = 0x3f3f3f3f; //无穷大
int G[N][N], dist[N]; //G[][]为邻接矩阵，dist[i]表示源点到结点i的最短路径长度
int p[N]; //p[i]表示源点到结点i的最短路径上i的前驱
int n, m; //n为结点数，m为边数
bool flag[N]; //如果flag[i]等于true，说明结点i已经加入到S集合;否则i属于V-S集合

void dijkstra(int u) {
	for (int i = 1; i <= n; i++) { //初始化
		dist[i] = G[u][i]; //初始化源点u到其他各个结点的最短路径长度
		flag[i] = false;
		if (dist[i] == INF)
			p[i] = -1; //源点u到该结点的路径长度为无穷大，说明源点u与结点i不相邻
		else
			p[i] = u; //说明结点i与源点u相邻，设置i的前驱为u
	}
	dist[u] = 0;
	flag[u] = true; //初始时，集合S中只有源点u
	for (int i = 1; i < n; i++) {
		int temp = INF, t = u;
		for (int j = 1; j <= n; j++) { //在集合V-S中寻找距离源点u最近的结点t
			if (!flag[j] && dist[j] < temp) {
				t = j;
				temp = dist[j];
			}	
		}
		if (t == u) return; //找不到t，跳出循环
		flag[t] = true;  //否则，将t加入S集合
		for (int j = 1; j <= n; j++) { //更新t的邻接点j的最短路径长度，松弛操作 
			if (!flag[j] && dist[j] > dist[t] + G[t][j]) {
				dist[j] = dist[t] + G[t][j];
				p[j] = t;
			}
		}
	}
}

void findpath(int u){//输出源点到其它各结点的路径 
	int x;
	stack<int>s;
	cout<<"源点为："<<u<<endl;
	for(int i=1;i<=n;i++){
    	x=p[i];
    	while(x!=-1){
    		s.push(x);
    		x=p[x];
    	}
	    cout<<"源点到其它各结点最短路径为：";
    	while(!s.empty()){
	    	cout<<s.top()<<"--";
      		s.pop();
    	}
		cout<<i<<";最短距离为："<<dist[i]<<endl;
	}
}

int main() {
	int u, v, w, st;//u、v表示结点，w表示u--v的距离，st表示源点
	int t;//测试用例数 
	cin >> t;
	while (t--) {
		cin >> n >> m; //n为节点个数，m为两点直接有相连权值的个数
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				G[i][j] = INF;//初始化邻接矩阵为无穷大
		while (m--) {
			cin >> u >> v >> w;
			G[u][v] = min(G[u][v], w); //邻接矩阵储存，保留最小的距离
		}
		cin >> st;//输入源点 
		dijkstra(st);
		for (int i = 1; i <= n; i++) {//输出源点到各结点的最短路径长度，即dist[]数组 
			if (i != 1) cout << " ";
			if (dist[i] == INF)
				cout << "impossible";
			else
				cout << dist[i];
		}
		cout << endl;
		findpath(st);
	}
	system("pause");
	return 0;
}