【算法】【ACM】深入理解Dijkstra算法（单源最短路径算法）

Dijkstra算法是用来求解从某个源点到其他各顶点的最短路径（单源最短路径）。

下面的Dijkstra算法的讲解都是基于这个有向图，在遇到其他问题可以类比。

算法的基本思想：

把图中的定点分成两组，第一组包括已确定最短路径的顶点，初始时只含有一个源点，记为集合S；第二组包括尚未确定的最短路径的顶点，记为V-S；按最短路径长度递增的顺序逐个把V-S中的顶点加到S中去，直至从v0出发可以到达的所有顶点都包括在S中。

【讲到这里要打断一下：我最初就是不能理解这个“按最短路径长度的递增顺序”（1）这个顺序到底是什么顺序？（2）哪个点到哪个点的最短路径长度？（3）如果是那个已经确定的源点到其他点的最短路径，但是源点并不是到每个点都有路径，在开始给邻接矩阵复制的时候，有的位置是INF，那这个怎么比较？？？？当时心里有无数个问号，找了很多博客，大家都没有详细说明（内心：这个这么好理解？我这么弱？）下面就会一一解答上面的问号。】

接着上面，在这个过程中，总保持v0到第一组S中各顶点的最短路径都不大（小于等于）与v0到第二组V-S的任何顶点的最短路径长度，第二组的顶点对应距离值是从v0到此顶点的只包括第一组S的顶点中为中间顶点的最短路径长度。对于S中任意一点 j，v0到j的路径长度皆小于v0到V-S中任意一点的路径长度。（这也与上面用红色标注的按照最短路径长度的递增顺序）

该表格表示：A到其余各点的最短路径

看到这里：上述所说的按照对端路径长度的递增顺序逐个把V-S中的顶点加到S中去，但是在拿到一个有向图时，我们怎么可能一眼看出路径长度是多少？需要代码求解。

为了实现该串代码，与要设置需要设置距离向量d[ ]（即：源点到该点的最短路径），以及保存路径的向量p[]（即：它的前一个点是谁（官方：最短路径上第i个顶点的前驱顶点序号））。

算法的具体步骤可描述如下：

（1）初始化：包括对第一组（集合S：目前集合S只有{v0}）的初始化与对距离向量d的初始化（用邻接矩阵中相应的值进行赋值）。

（2）从第二组V-S的顶点中选取一个距离值最小的顶点v加入S，。接着对V-S中的所有顶点值进行修改，修改的方法是，对于V-S中的任意一个顶点k，若图中有边<v,k>，且v0到v的距离加上<v，k>边上的权值之和小于v0到k的距离值，则用“v0到v的距离加上<v，k>边上的权值代替顶点k原来的距离值”，（v作为中间点）；反之，则顶点k的距离值保持不变。

。

【我的理解：就是一开始d[k]中肯定就和邻接矩阵中的值一样，有数字，也有INF(即不存在到该点的路径，但是随着S集合中不断加入顶点（按照最短路径的长度递增顺序），源点通过加入的这些顶点就可以到达更多的顶点，每加入一个顶点，就要算一下通过这个刚刚加入的中间点，v0到其他点的距离是否有变短，如果有，则修改相应的值，反之，则保持不变。要保证加入到S中的每个点，源点v0到它们的路径长度是最短的。】

（3）若集合V-S已空，则结束算法。若V-S不为空，则返回步骤（2）。

有向网G采用邻接矩阵存储结构

#include <stdio.h>
#include <stdlib.h>
#define  M 20
#define FINITY 50000
typedef struct 
{char vexs[M];int edges[M][M];int n,e;
}Mgraph;

创建网络的邻接矩阵算法

void creat(Mgraph *g,int c)
{int i,j,k,w;FILE *f;f=fopen("test.txt","r");if(f){fscanf(f,"%d%d",&g->n,&g->e);for(i=0;i<g->n;i++)fscanf(f,"%1s",&g->vexs[i]);for(i=0;i<g->n;i++){for(j=0;j<g->n;j++){if(i==j)	g->edges[i][j]=0;else		g->edges[i][j]=FINITY;}}for(k=0;k<g->e;k++){fscanf(f,"%d%d%d",&i,&j,&w);g->edges[i][j]=w;if(c==0)	g->edges[j][i]=w;}fclose(f);}else{g->n=0;}
}

输出邻接矩阵

void print(Mgraph g)
{printf("\n");for(int i=0;i<g.n;i++){for(int j=0;j<g.n;j++){printf("%7d",g.edges[i][j]);}printf("\n");}
}

这里图中显示的 “50000” 即为 INF

Dijkstra算法代码实现

void dijkstra1(Mgraph g,int v0)
{print(g);int i,j,k,v,min,x;//第一步：初始化集合S与距离向量dfor(v=0;v<g.n;v++){vis[v]=0;d[v]=g.edges[v0][v];//d[v]==0 则是edges[i][j]中i==j的情况//d[v]==FINITY 则是v0和v之间没有路径可达if(d[v]<FINITY && d[v]!=0)p[v]=v0;elsep[v]=-1;//没有前驱结点}vis[v0]=1;d[v0]=0;//初始时集合S中只有一个v0printf("\n初始d[]数组：\n");for(k=0;k<g.n;k++)printf("k=%d %d\n",k,d[k]);//第二步：依次找出n-1个结点加入S中for(i=1;i<g.n;i++){min=FINITY;for(k=0;k<g.n;k++){//在d[k]中找出没有被选入S集合中的，距离v0最近的点//这就体现了“按照最短路径长度的递增顺序”if(!vis[k] && d[k]<min){v=k;min=d[k];}}//输出此次被选入的顶点距离printf("\n%c %d\n",g.vexs[v],min);if(min==FINITY)	return ;vis[v]=1;//已经被选进入集合S//第三步：修改S与V-S中各结点的距离for(k=0;k<g.n;k++){if(!vis[k] && (min+g.edges[v][k])<d[k]){d[k]=min+g.edges[v][k];p[k]=v;}}//这里是输出每一次数组d[]，可以清楚观察d[]中各元素的变化情况printf("*********\n");for(k=0;k<g.n;k++)printf("k=%d %d\n",k,d[k]);printf("*********\n");}printf("\n最终d[]数组：\n");for(k=0;k<g.n;k++)printf("k=%d %d\n",k,d[k]);
}

初始状态就是因为选择的是v0（A结点：序号0），所以和邻接矩阵第一行一样。

C F B D E 是依次加入集合S顺序

vis[0]已经被标记为1了

i=1：找到的v=2，min=4，vis[2]=1

接着比较通过顶点2(C)到其他结点的距离是否有改变

min+g.edges[2][1]=4+15=19<INF ，所以d[1]=19

min+fg.edges[2][5]=4+8=12<INF，所以d[5]=12（就是第二张图的情况）

i=2：v=5，min=12，vis[5]=1

接着比较通过顶点5(F)到其他结点的距离是否有改变

min+g.edges[5][3]=12+13=25，所以k[3]=25

min+g,edges[5][4]=12+18=30，所以k[4]=30（就是第三张图的情况）

。。。。。。

以此类推，大家可以结合图自己算一下。

对应着图来比较 “原来源点到某一点的距离”与“源点到新加入S的这个点的距离+这个点到图中某一点的距离”是否有缩短。最终的d[ ]数组就是顶点A到各个点的最短距离。

这里只是举了d[ ]数组，p[ ]数组也是一样。

全部代码

#include <stdio.h>
#include <stdlib.h>
#define  M 20
#define FINITY 50000
typedef struct 
{char vexs[M];int edges[M][M];int n,e;
}Mgraph;void creat(Mgraph *g,int c)
{int i,j,k,w;FILE *f;f=fopen("test.txt","r");if(f){fscanf(f,"%d%d",&g->n,&g->e);for(i=0;i<g->n;i++)fscanf(f,"%1s",&g->vexs[i]);for(i=0;i<g->n;i++){for(j=0;j<g->n;j++){if(i==j)	g->edges[i][j]=0;else		g->edges[i][j]=FINITY;}}for(k=0;k<g->e;k++){fscanf(f,"%d%d%d",&i,&j,&w);g->edges[i][j]=w;if(c==0)	g->edges[j][i]=w;}fclose(f);}else{g->n=0;}
}void print(Mgraph g)
{printf("\n");for(int i=0;i<g.n;i++){for(int j=0;j<g.n;j++){printf("%7d",g.edges[i][j]);}printf("\n");}
}
int vis[M];//表示当前元素是否已求出最短路径
int p[M];//路径向量
int d[M];//距离向量
void dijkstra1(Mgraph g,int v0)
{print(g);int i,j,k,v,min,x;//第一步：初始化集合S与距离向量dfor(v=0;v<g.n;v++){vis[v]=0;d[v]=g.edges[v0][v];//d[v]==0 则是edges[i][j]中i==j的情况//d[v]==FINITY 则是v0和v之间没有路径可达if(d[v]<FINITY && d[v]!=0)p[v]=v0;elsep[v]=-1;//没有前驱结点}vis[v0]=1;d[v0]=0;//初始时集合S中只有一个v0printf("\n初始d[]数组：\n");for(k=0;k<g.n;k++)printf("k=%d %d\n",k,d[k]);//第二步：依次找出n-1个结点加入S中for(i=1;i<g.n;i++){min=FINITY;for(k=0;k<g.n;k++){//在d[k]中找出没有被选入S集合中的，距离v0最近的点//这就体现了“按照最短路径长度的递增顺序”if(!vis[k] && d[k]<min){v=k;min=d[k];}}//输出此次被选入的顶点距离printf("\n%c %d\n",g.vexs[v],min);if(min==FINITY)	return ;vis[v]=1;//已经被选进入集合S//第三步：修改S与V-S中各结点的距离for(k=0;k<g.n;k++){if(!vis[k] && (min+g.edges[v][k])<d[k]){d[k]=min+g.edges[v][k];p[k]=v;}}//这里是输出每一次数组d[]，可以清楚观察d[]中各元素的变化情况printf("*********\n");for(k=0;k<g.n;k++)printf("k=%d %d\n",k,d[k]);printf("*********\n");}printf("\n最终d[]数组：\n");for(k=0;k<g.n;k++)printf("k=%d %d\n",k,d[k]);
}int main ()
{Mgraph g;creat(&g,1);dijkstra1(g,0);return 0;
}

这是数据结构中的代码，与一般ACM题目中的代码大同小异，下面就举几个例题，来亲自实践一下

现学活用

一、杭电OJ 3790 最短路径问题

http://acm.hdu.edu.cn/showproblem.php?pid=3790

套用上面Dijkstra算法的模板，加上一点点小的改动，上面的代码针对的时有向图，这道题无向图，所以赋值的时候要注意，还有引入了花费，不止问最短路径，在判断上需要注意一下

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 1000;
const int FINITY = 500000;
int map[1010][1010];
int price[1010][1010];
int dis[1010],p1[1010];
int vis[1010];
int n,m,a,b,d,s,t,p;
void dijkstra()
{int i,j,k,min,v;for(i=1;i<n;i++){min=FINITY;for(k=1;k<=n;k++){if(!vis[k] && min>dis[k]){min=dis[k];v=k;}}vis[v]=1;for(k=1;k<=n;k++){if(!vis[k] && (min+map[v][k])<dis[k]){dis[k]=min+map[v][k];p1[k]=p1[v]+price[v][k];}else if(dis[k]==min+map[v][k]){if(p1[k]>p1[v]+price[v][k])p1[k]=p1[v]+price[v][k];}}}
}int main ()
{int i,j;while(scanf("%d%d",&n,&m)!=EOF){if(m==0 && n==0)	break;for(i=0;i<=n;i++){for(j=0;j<=n;j++){if(i==j)	{map[i][j]=0;price[i][j]=0;}else	{map[i][j]=FINITY;price[i][j]=FINITY;}}}for(int q=0;q<m;q++){scanf("%d%d%d%d",&a,&b,&d,&p);if(d<map[a][b]){map[a][b]=d;map[b][a]=d;price[a][b]=p;price[b][a]=p;}}memset(vis,0,sizeof(vis));scanf("%d%d",&s,&t);vis[s]=1;for(i=1;i<=n;i++){dis[i]=map[s][i];p1[i]=price[s][i];}dijkstra();printf("%d %d\n",dis[t],p1[t]);}return 0;
}

二、杭电OJ 2544 最短路

http://acm.hdu.edu.cn/showproblem.php?pid=2544

这一题就是完全套用模板，模板里还有一个路径向量p，这个题不需要用到路径向量p，所以相比较上一题来说比较简单

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int INF = 5000000;
int map[105][105];
int dis[105];
int vis[105];
int N,M;void dijkstra()
{int i,j,min,v;for(i=1;i<N;i++){min=INF;for(j=1;j<=N;j++){if(!vis[j] && dis[j]<min){min=dis[j];v=j;}}vis[v]=1;for(j=1;j<=N;j++){if(!vis[j] && (min+map[v][j])<dis[j]){dis[j]=min+map[v][j];}}}
}int main ()
{int i,j,a,b,t;while(scanf("%d%d",&N,&M)!=EOF){if(N==0 && M==0)	return 0;for(i=0;i<=N;i++){for(j=0;j<=N;j++){if(i==j)	map[i][j]=0;else		map[i][j]=INF;}}for(i=0;i<M;i++){scanf("%d%d%d",&a,&b,&t);if(t < map[a][b]){map[a][b]=t;map[b][a]=t;}}memset(vis,0,sizeof(vis));for(i=1;i<=N;i++)dis[i]=map[1][i];vis[1]=1;dijkstra();printf("%d\n",dis[N]);}return 0;
}

三、杭电OJ 1874 畅通工程续

这个题目是存在可能找不到最短路径的情况，所以需要在最后判断dis[t]的值是否为INF，是的话就不存在，不是的话就输出它的值。

http://acm.hdu.edu.cn/showproblem.php?pid=1874

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF = 500000;
int map[205][205];
int dis[205];
int vis[205];
int n,m,a,b,x,s,t;
void dijkstra()
{int i,j,min,v;for(i=1;i<n;i++){min=INF;for(j=0;j<n;j++){if(!vis[j] && min > dis[j]){min=dis[j];v=j;}}if(min==INF)	return ;vis[v]=1;for(j=0;j<n;j++){if(!vis[j] && (min+map[v][j])<dis[j]){dis[j]=min+map[v][j];}}}
}int main ()
{int i,j;while(scanf("%d%d",&n,&m)!=EOF){for(i=0;i<=n;i++){for(j=0;j<=n;j++){if(i==j)	map[i][j]=0;else	map[i][j]=INF;}}for(i=1;i<=m;i++){scanf("%d%d%d",&a,&b,&x);if(x < map[a][b]){map[a][b]=x;map[b][a]=x;}}scanf("%d%d",&s,&t);memset(vis,0,sizeof(vis));for(i=0;i<n;i++)dis[i]=map[s][i];vis[s]=1;dijkstra();if(dis[t]==INF)printf("-1\n");elseprintf("%d\n",dis[t]);}return 0;
}

四、POJ  2387   Til the Cows Come Home

http://poj.org/problem?id=2387

这个题最重要的就是读懂题意，看清楚哪个字母代表点的数目，哪个字母是边的数目，数组要开的足够大，不然会Runtime Error

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF = 0xfffffff;
int map[1010][1010];
int dis[1010];
int vis[1010];
int n,m,a,b,x,s,t;
void dijkstra()
{int i,j,min,v;for(i=1;i<n;i++){min=INF;for(j=1;j<=n;j++){if(!vis[j] && min > dis[j]){min=dis[j];v=j;}}if(min==INF)	break;vis[v]=1;for(j=1;j<=n;j++){if(!vis[j] && (min+map[v][j])<dis[j]){dis[j]=min+map[v][j];}}}
}int main ()
{int i,j;while(scanf("%d%d",&m,&n)!=EOF){for(i=0;i<=n;i++){for(j=0;j<=n;j++){if(i==j)	map[i][j]=0;else	map[i][j]=INF;}}for(i=1;i<=m;i++){scanf("%d%d%d",&a,&b,&x);if(x < map[a][b] && x){map[a][b]=x;map[b][a]=x;}}memset(vis,0,sizeof(vis));for(i=1;i<=n;i++)dis[i]=map[1][i];vis[1]=1;dijkstra();printf("%d\n",dis[n]);}return 0;
}

从上面四道题可以看出，运用Dijkstra算法时，就是套用模板，但是一定要清楚Dijkstra算法的步骤及其内涵，才能运用自如，我现在也不敢说我完全掌握了Dijkstra算法，需要反复地揣摩，做一些题进行复习，有错的地方希望大家及时指正！！！谢谢