图论算法讲解--最短路--Dijkstra算法
一.绪论
要学习最短路算法我们首先应该知道什么是图以及什么是最短路。
图在离散数学中的定义为：图G=（V,E）是一个二元组（V,E）使得E⊆[V]的平方，所以E的元素是V的2-元子集。为了避免符号上的混淆，我们总是默认V∩B=Ø。集合V中的元素称为图G的定点（或节点、点），而集合E的元素称为边（或线）。通常，描绘一个图的方法是把定点画成一个小圆圈，如果相应的顶点之间有一条边，就用一条线连接这两个小圆圈，如何绘制这些小圆圈和连线时无关紧要的，重要的是要正确体现哪些顶点对之间有边，哪些顶点对之间没有边。
简单来讲，一个图就是由两个集合构成，集合V储存图中的所有顶点，集合E储存图中所有的边。
最短路的定义为：在一个图中，每条边都有一个权值，给出一个起点和终点，求出起点到终点之间权值最小的路径，即是最短路。
二.Dijkstra概述
Dijkstra算法用于解决单源最短路问题，所谓单源最短路就是指定一个起点，求出这个起点到其它所有点的最短路。
使用Dijkstra算法还要求图中不能有权值为负的边，否则会出现死循环。
三.Dijkstra算法流程
首先给出几个定义：
1.s：表示单源最短路的起点。
2.d[v]：表示从起点到v点的距离，初始化d[1~n]=inf，d[s]=0，当Dijkstra算法结束后，d[v]所存储的即时由起点到v的最短路长度。
3.vst[v]：记录顶点v是否已经更新过，初始化vst[1~n]=0，表示所有点都未被更新过。
4.val(u,v)：表示从u点连向v点边的权值。
算法流程：
1.从图中找出所有u可达的顶点v0~vm，对于v0~vm，若有d[v]> d[u]+val(u,v)，则表示发现更短的路线，更新d[v]为d[u]+val(u,v)。
2.找出d[v]最小，且vst[v]=0的点，让v作为新的起点，将vst[v]=1，表示顶点v已被更新。
3.重复上述过程，直到所有顶点都被更新。
从上述流程中不难发现，所谓Dijkstra算法，就是依次让每个顶点作为起点，更新最短路的过程。
具体过程，请结合算法流程来看图文演示，相信看完之后大家一定会理解Dijkstra算法的思想。
四.图文演示
1.
初始状态，将d[1~n]=inf，d[s]=0
以点M作为起点，即s=M
d数组: vst数组:
d[M]=0 vst[M]=0
d[W]=inf vst[W]=0
d[E]=inf vst[E]=0
d[D]=inf vst[D]=0
d[X]=inf vst[X]=0
2.
d数组: vst数组:
d[M]=0 vst[M]=0
d[W]=inf vst[W]=0
d[E]=inf vst[E]=0
d[D]=inf vst[D]=0
d[X]=inf vst[X]=0
找出d中值最小且未被使用的点，发现d[M]=0最小，且vst[M]=0，未被使用，故将M作为新的起点
找出所有M可达的顶点，为X、W、E
d[X]=inf > 0+10 ，更新d[X]=10
d[W]=inf > 0+5 ，更新d[W]=5
d[E]=inf > 0+8 ，更新d[E]=8
M已被使用，vst[M]=1
3.
d数组: vst数组:
d[M]=0 vst[M]=1
d[W]=5 vst[W]=0
d[E]=8 vst[E]=0
d[D]=inf vst[D]=0
d[X]=10 vst[X]=0
找出d中值最小且未被使用的点，发现d[W]=5最小，且vst[W]=0，未被使用，故将W作为新的起点
找出所有W可达顶点，为M、X、D、E
vst[M]=1，已被更新过，故忽略
d[X]=10 > 5+3 ，更新d[X]=8
d[D]=inf > 5+9 ，更新d[D]=14
d[E]=8 >5+2 ，更新d[E]=7
W已被使用，vst[W]=1
4.
d数组: vst数组:
d[M]=0 vst[M]=1
d[W]=5 vst[W]=1
d[E]=7 vst[E]=0
d[D]=14 vst[D]=0
d[X]=8 vst[X]=0
找出d中值最小且未被使用的点，发现d[E]=7最小，且vst[E]=0，未被使用，故将E作为新的起点
找出所有E可达的顶点，为W、M、D
vst[W]=1，已被更新过，忽略
vst[M]=1，已被更新过，忽略
d[D]=14 > 7+6 ，更新d[D]=13
E已被使用，vst[E]=1
5.
d数组: vst数组:
d[M]=0 vst[M]=1
d[W]=5 vst[W]=1
d[E]=7 vst[E]=1
d[D]=13 vst[D]=0
d[X]=8 vst[X]=0
找出d中值最小且未被使用的点，发现d[X]=8最小，且vst[X]=0，未被使用，故将X作为新的起点
找出所有X可达的顶点，为W、M、D
vst[W]=1，已被更新过，忽略
vst[M]=1，已被更新过，忽略
d[D]=13 >8+1 ，更新d[D]=9
X已被使用，更新vst[X]=1
6.
d数组: vst数组:
d[M]=0 vst[M]=1
d[W]=5 vst[W]=1
d[E]=7 vst[E]=1
d[D]=9 vst[D]=0
d[X]=8 vst[X]=1
找出d中值最小且未被使用的点，发现d[D]=9最小，且vst[D]=0，未被使用，故将D作为新的起点
找出所有D可达的顶点，为E、W、X
vst[E]=1，已被使用，忽略
vst[W]=1，已被使用，忽略
vst[X]=1，已被使用，忽略
D已被使用，更新vst[D]=1
7.
d数组: vst数组:
d[M]=0 vst[M]=1
d[W]=5 vst[W]=1
d[E]=7 vst[E]=1
d[D]=9 vst[D]=1
d[X]=8 vst[X]=1
发现所有顶点都被使用过，算法结束，此时d数组中保存的就是以M为起点，到达所有其它点的单源最短路长度
五.算法实现及优化
致此，我相信大家都理解了算法的流程了，下面通过代码来看如何具体实现Dijkstra，详见注释。
普通版本：O(n^2)
#include<stdio.h>
#include<iostream>
#include<cstring>
using namespace std;
const int maxv=1000;
const int inf=0x3f3f3f3f;
int cost[maxv][maxv]; //邻接矩阵存图
int d[maxv];
bool vst[maxv];
int N; //顶点的个数
void dijkstra(int s)
{
memset(d,inf,sizeof(d)); //初始化d[1~N]=inf
d[s]=0; //初始化d[s]=0
fill(used,used+v,false); //初始化vst[1~N]=0
while(true)
{
int now=-1;
for(int u=0;u<N;u++)
{
if(!used[u]&&(now==-1||d[u]<d[now])) //找到d最小，且vst=0的点作为新的起点
now=u;
}
if(now=-1) break; //now未被更新，即表示所有顶点都被使用过，算法结束
for(int v=0;v<N;v++) //遍历当前起点now能到达的所有点
{
if(d[v]>d[now]+cost[now][v]) //若d[v]>d[u]+val(u,v)，则更新
d[v]=d[now]+cost[now][v]
}
vst[now]=1; //当前起点now已被使用过，vst[now]=1
}
}路径还原：
除了最短路的长度，还要求出最短路的路径
#include<stdio.h>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int maxv=1000;
const int inf=0x3f3f3f3f;
int cost[maxv][maxv]; //邻接矩阵存图
int prev[maxv]; //储存前驱点编号，是路径还原的关键
int d[maxv];
bool vst[maxv];
int N; //顶点的个数
void dijkstra(int s)
{
memset(d,inf,sizeof(d)); //初始化d[1~N]=inf
d[s]=0; //初始化d[s]=0
fill(used,used+v,false); //初始化vst[1~N]=0
while(true)
{
int now=-1;
for(int u=0;u<N;u++)
{
if(!used[u]&&(now==-1||d[u]<d[now])) //找到d最小，且vst=0的点作为新的起点
now=u;
}
if(now=-1) break; //now未被更新，即表示所有顶点都被使用过，算法结束
for(int v=0;v<N;v++) //遍历当前起点now能到达的所有点
{
if(d[v]>d[now]+cost[now][v]) //若d[v]>d[u]+val(u,v)，则更新
{
d[v]=d[now]+cost[now][v];
prev[v]=now; //同时更新前驱结点编号
}
}
vst[now]=1; //当前起点now已被使用过，vst[now]=1
}
}
vector <int>get_path(int t) //路径还原函数，将最短路径存在path中
{
vector<int>path;
for(;t!=-1;t=prev[t])
path.push_back(t);
reverse(path.begin(),path.end());
return path;
}优先队列优化：O（ElogV）
#include <bits/stdc++.h>
#include <vector>
#include <queue>
using namespace std;
const int MAX_N=1000;
const int MAX_V=1000;
const int INF=0x3f3f3f3f;
struct edge
{
int to,cost;
};
typedef pair<int,int>P; //first是最短距离，second是顶点编号
int N; //顶点的个数
vector<edge>G[MAX_N]; //存图的方法有很多种，大家可以用自己喜欢的方式
int d[MAX_V];
void Dijstra(int s)
{
//通过指定greater<P>参数，堆按照first从小到大顺序取出值
priority_queue< P,vector<P>,greater<P> > que;
fill(d,d+N,INF); //初始化，d[1~N]设为inf
d[s]=0; //初始化，d[s]=0
que.push(P(0,s));
while(!que.empty())
{
P now=que.top(); //now表示当前起点
que.pop();
int u=now.second;
if(d[u]<now.first) continue;
for(int i=0;i<G[u].size();i++) //遍历当前起点能到达的所有点
{
edge e=G[u][i];
if(d[e.to]>d[u]+e.cost) //如果d[v]>d[u]+val(u,v)则更新
{
d[e.to]=d[u]+e.cost;
que.push(P(d[e.to],e.to));
}
}
}
}