最短路径之迪杰斯特拉算法模板(一)

最短路径是图论中一个很经典的问题：给定图G(V，E)，求一条从起点到终点的路径，使得这条路径上经过的所有边的边权之和最小。即，对任意给出的图G(V，E)和起点S、终点T，如何求从S到T的最短路径。

这里简单说一下迪杰斯特拉算法(Dijkstra)解决单源点最短路径问题，即给定图G和起点S，通过算法得到S到达其它每个顶点的最短距离。

基本思想：

对图G(V，E)设置集合S，存放已被访问的顶点，然后每次从集合V-S中选择与起点s的最短距离最小的一个顶点(记为u)，访问并加入集合S。之后，令顶点u为中介点，优化起点s与所有从u能到达的顶点v之间的最短距离。这样的操作执行n次(n为顶点个数)，直至集合S包含所有顶点。

因为图可以用邻接矩阵和邻接表存储，所以这里打算将两种方式都记录一下。

（一）邻接矩阵版的代码(一般用于顶点数不超过1000)：

#include<iostream>
#include<algotithm>
//邻接矩阵版 
const int maxn = 1000;	//最大顶点数，一般来说用邻接矩阵则顶点数最好不超过1000 
const int INF = 1000000000;
int n, G[maxn][maxn];	//n为顶点数，G[u][v]表示顶点u到顶点v的距离 
int d[maxn];	//d[u]表示起点s到达u的距离
bool vis[maxn] = {false};	//vis[u]=false表示顶点u还未访问;反之则表示u已访问

//若需要输出最短路径上的每个顶点，则需用pre数组保存
int pre[maxn];    //pre[v]表示从起点到顶点v的最短路径上v的前一个顶点

void Dijkstra(int s){	//s是起点 
	//初始化
	fill(d, d + maxn, INF);
	d[s] = 0;	//起点s离起点距离为0
    for(int i = 0; i < n; i++) pre[i] = i;

	//执行n次操作 
	for(int i = 0; i < n; i++){	
		//1.先选择离起点最近的 未被访问的 顶点u
		int u = -1, MIN = INF;
		for(int j = 0; j < n; j++){
			if(vis[j] == false && d[j] < MIN){
				u = j;
				MIN = d[j];
			}
		}
		//找不到小与INF的d[u]，说明剩下的顶点和起点s不连通 
		if(u == -1)	return;	

		//2. 访问u
		vis[u] = true;
			
		for(int v = 0; v < n; v++){
			//3.如果v未被访问 && u能到达v && 以u为中介点能优化d[v] 
			if(vis[v] == false && G[u][v] != INF && d[u] + G[u][v] < d[v]){
				d[v] = d[u] + G[u][v];	//优化起点到顶点v的距离
                pre[v] = u; 
			}
		} 
	} 
}
//输出最短路径上的每个顶点
void DFS(int s, int v){    //s是起点编号， v是当前访问的顶点编号(从终点开始递归)
    if(v == s){
        printf("%d\n", v);
        return;
    }
    DFS(s, pre[v]);
    printf("%d\n", v);
}
 
           

（二）邻接表版的代码：

#include<iostream>
#include<vector>
#include<algotithm>
//邻接表版 
const int maxn = 1000;
const int INF = 1000000000;
struct Node{
	int v, dis;	//v是边的目标顶点，dis是边权 
};
int n;	//顶点数 
vector<Node> Adj[maxn];
int d[maxn];
bool vis[maxn] = {false};

void Dijkstra(int s){
	//初始化
	fill(d, d + maxn, INF);
	d[s] = 0;
	
	for(int i = 0; i < n; i++){	//执行n次操作 
		//选出距离起点最近的 未被访问的点
		int u = -1, MIN = INF;
		for(int j = 0; j < n; j++){
			if(vis[j] == false && d[j] < MIN){
				u = j;
				MIN = d[j];
			}
		}
		if(u == -1) return;
		vis[u] = true;
		//遍历与u相连的各个顶点 (和邻接矩阵版的比，只有下面代码写法稍有不同!!!)
		for(int j = 0; j < Adj[u].size(); j++){
			int v = Adj[u][j].v;	//与u相连的顶点编号是v 
			int dis = Adj[u][j].dis;	//u和v之间边权是dis
			if(vis[v] == false && d[u] + dis < d[v]){
				d[v] = d[u] + dis;
			} 
		} 
	} 
} 
           

两种形式代码如上所示。仔细对比可以发现只有少许不同。

仔细研究可以发现采用此模板有些缺点：所求的最短路径只能是唯一一条，若有多条则不适用！！！