图论（三）——单源最短路径之Dijkstra算法

单源最短路径问题，即给定一张有向图（其实无向图也可以看作是有向图，即将无向的一条边看成是两条有向的边），设1号节点为起点，求其到i号节点的最短距离

Dijkstra 算法

Dijkstra 算法，算是这种单源最短路径问题中最为经典的一种算法了，其主要思想大致如下：

设1号节点为起点，设一个长度为numNode的数组dis，其中dis[i]表示从起点1到节点i的最短距离，设一个长度为numNode的数组vis，其中vis[i]用来记录以节点i为起点的边是否被处理过

1. 初始化dis[1]=0，其余元素值为正无穷大，将vis数组的元素值初始化为0
2. 找出一个未被标记的（vis[i]=0）、dis[i]最小的节点i，然后标记节点i（vis[i]=1）
3. 扫描以节点i为起点的所有边（i,to,weight），若dis[i]+weight<dis[to]，则令dis[to]=dis[i]+weight（ 即dis[to]=min(dis[to],dis[i]+weight) ）
4. 重复步骤2和步骤3，直到所有的节点都被标记

以上则是Dijkstra算法的思想了， 使用Dijkstra算法时还需要注意：因为Dijkstra算法基于贪心算法，所以其只适用于所有边的长度都是非负数的图。

代码实现

就举个例子来说吧：HDU最短路

这就是一个最最基本的Dijkstra算法的运用了

代码：（存图的方式其实可以不用代码中的链式向前星而是用邻接矩阵（节点的数目较少））

【存边的方法： 图论（一）——边的储存 】

#include<cstdio>
#include<cstring>
#include<climits>
using namespace std;
const int lenNode=110;
const int lenEdge=20010;  //注意这是一个无向图 

int n,m,dis[Len],vis[Len];
 
int cnt,head[lenEdge];
struct Edge{
	int to,weight;
	int nxt;
}edge[lenEdge]; 


void init(){
	memset(dis,INT_MAX,sizeof(dis));
	dis[1]=0;
	memset(vis,0,sizeof(dis));
	
	for(int i=0;i<lenEdge;i++){
		edge[i].nxt=-1;
	}
	memset(head,-1,sizeof(head));
	cnt=0;
}

void addEdge(int u,int v,int w){
	edge[cnt].to=v;
	edge[cnt].weight=w;
	edge[cnt].nxt=head[u];
	head[u]=cnt++;
}

void Dijkstra(){
	int index;
	 
	for(int i=1;i<n;i++){   //一共是n-1个其他的节点要处理 所以重复进行n-1次 
		index=0;
		 
		for(int j=1;j<=n;j++){  //找到未标记的节点中dis最小的节点 
			if( !vis[j] && (index==0 || dis[j]<dis[index]) ){
				index=j;
			}
		}
		
		vis[index]=1;  //用这个 index 节点的边来更新所有与之相连的节点 
		for(int j=head[index];j!=-1;j=edge[j].nxt){
			dis[edge[j].to]=min(dis[edge[j].to],dis[index]+edge[j].weight);
		}
	}
}

int main(){
	int a,b,c;
	while(~scanf("%d%d",&n,&m)&&n){
		init();
		 
		for(int i=1;i<=m;i++){
			scanf("%d%d%d",&a,&b,&c);
			addEdge(a,b,c);
			addEdge(b,a,c);  //注意这是一个无向图 
		}
		
		Dijkstra();
		printf("%d\n",dis[n]);
	}
	
	return 0;
}
           

以上的代码的时间复杂度为O(numNode^2)，时间复杂度的主要瓶颈在于在函数Dijkstra中寻找未标记的节点中dis最小的节点，这一步可以用二叉堆（优先队列，priority_queue）对dis数组进行维护，更加节省时间。

【解决单源最短路径问题的其他方法：图论（三）——单源最短路径之Bellman-Ford算法和SPFA算法】