Dijkstra算法求最短路径
求最短路径的算法很多，常见的有Dijkstra，Bellmen，Floyd等，他们原理和时间空间复杂度各有不同，其中最有代表性也比较好理解的就是Dijkstra算法。Chuck在百度面试时因为有过ACM经历所以被问到算法这部分，手写了一段Dijkstra算法的实现。
Dijkstra算法适合处理稠密图而且可以处理双向图，但缺点是不能处理带有负边权值的路径问题。Dijkstra算法是基于贪心算法的一种实现，其运算过程也包含了动态规划的思想，时间复杂度为O(n^2)。
其算法执行过程不难理解，讲解原理之前先定义如下变量。Dijkstra算法需要定义一个二维数组e[n][n]（n表示一共n个点），每个单元存放一个值，e[i][j]表示i点到j点的距离，e[i][i]的点距离均设为0（自己到自己距离为0），还需要一个一维数组dis[n]，来记录起始点到每个点的最短路径，输出时输出dis[终点]即可，此外还需要定义一个vis[n]数组用来统计每个点是否用到过。
通过一个例子，Chuck带大家推理一下Dijkstra算法的计算过程：
现在给出几条边的值，求a到b点的最短路径：
start end weight
1 2 1
1 3 12
2 3 9
2 4 3
4 3 4
4 5 13
5 6 4
4 6 15
3 5 5
根据所给数据填入二维数组e中，填入后数组e的情况为：
1 2 3 4 5 6
1 0 1 12 max max max
2 max 0 9 3 max max
3 max max 0 max 5 max
4 max max 4 0 13 15
5 max max max max 0 4
6 max max max max max 0
点与点之间不可到达时，其距离设为无穷大，以不干扰最短路径的计算。
以试求1到6的最短路径为例，将1设置为源点。以源点到各点的距离对dis[ ]和vis[ ]数组进行初始化。这一点很像动态规划中对结果集的初始化过程，但还是略有区别。初始化后的数组状态：
dis 1 2 3 4 5 6
0 1 12 max max max
----------------------------------------------
//‘1’代表访问过，‘0’表示尚未访问
vis 1 2 3 4 5 6
1 0 0 0 0 0
第一步：寻找除1点外离源点最近的点并求以这个点为起点的边到其他个点的距离。通过dis[ ]数组可知，现在2点离1点最近，看以2为起点的边2——>3，2——>4。目前dis[3]=12，而若从1先到2再从2到3距离则为dis[2]+e[2][3]=10<dis[3]！因此更新dis[3]的值。dis[4]现在为max，从1到2再到4距离为dis[2]+e[2][4]<dis[4]，因此更新dis[4]！得到新的dis[]数组为：
dis 1 2 3 4 5 6
0 1 10 4 max max
----------------------------------------------
//‘1’代表访问过，‘0’表示尚未访问
vis 1 2 3 4 5 6
1 1 0 0 0 0
第二步：再寻找3,4,5,6中距离源点最近的点。此时4离源点最近还按照刚才的做法4——>3，4——>5，4——>6。dis[3]更新为dis[4]+e[4][3]=8；dis[5]=dis[4]+e[4][5]=17；dis[6]=dis[4]+e[4][6]=19。此时数组变为：
dis 1 2 3 4 5 6
0 1 8 4 17 19
----------------------------------------------
//‘1’代表访问过，‘0’表示尚未访问
vis 1 2 3 4 5 6
1 1 0 1 0 0
第三步：从3,5,6中找离源点最近的点为3。3出发3——>5。dis[5]>dis[3]+e[3][5]，dis[5]更新为13。
dis 1 2 3 4 5 6
0 1 8 4 13 19
----------------------------------------------
//‘1’代表访问过，‘0’表示尚未访问
vis 1 2 3 4 5 6
1 1 1 1 0 0
第四步：5,6中5距离原点更近，5出发5——>6，dis[6]>dis[5]+e[5][6]，dis[6]变为17。
dis 1 2 3 4 5 6
0 1 8 4 13 17
----------------------------------------------
//‘1’代表访问过，‘0’表示尚未访问
vis 1 2 3 4 5 6
1 1 1 1 1 0
第五步：只剩6了，从6无出发路线故无法操作，dis[ ]最终定为：
dis 1 2 3 4 5 6
0 1 8 4 13 17
----------------------------------------------
//‘1’代表访问过，‘0’表示尚未访问
vis 1 2 3 4 5 6
1 1 1 1 1 1
从源点1到终点6的距离即为dis[6] = 17。当然了，根据题目不同源点终点，题目求解方式略有不同但万变不离其宗。接下来考虑代码实现：
#include <iostream>
#include<stdio.h>
#define Max 9999999
using namespace std;
int dis[1005],vis[1005];
int e[1005][1005];
int n,m,a,b,u,v,w,Min;
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n==0&&m==0) break;
for(int i=1;i<=n;i++)
{
vis[i]=0;
for(int j=1;j<=n;j++)
{
e[i][j]=Max;
}
}
//将边输入数组e
while(m--)
{
scanf("%d%d%d",&u,&v,&w);
if(e[u][v]>w)
{
e[u][v]=e[v][u]=w;
}
}
scanf("%d%d",&a,&b);
//初始化vis[ ]和dis[ ]
vis[a]=1;
for(int i=1;i<=n;i++)
{
dis[i]=e[a][i];
}
//Dijkstra方法核心代码
for(int i=1;i<=n-1;i++)
{
//求距离源点最近的且未访问过的点
Min=Max;
for(int j=1;j<=n;j++)
{
if(vis[j]==0&&dis[j]<Min)
{
Min=dis[j];u=j;
}
}
//设置该点已被访问
vis[u]=1;
//更新从该点到其余各点的最短距离
for(v=1;v<=n;v++)
{
if(e[u][v]<Max)
{
if(dis[v]>dis[u]+e[u][v])
{
dis[v]=dis[u]+e[u][v];
}
}
}
}
printf("%d %d\n",dis[b],value[b]);
}
return 0;
}
Dijkstra算法在众多算法中相对好理解，如果理解其原理，完全可以在面试现场一边推一边写。Dijkstra算法运用也很广，所以大企业的面试官如果问到这部分一般都会选择Dijkstra算法作为考点提问。
