浅谈dijkstra——解决最短路问题的有力算法
基本思想和流程：
\(dijkstra\) 算法是一种可以在 \(O(m\log n)\) 的时间内求出单源最短路的算法。
此算法运用了贪心的思想，从起点开始扩展，每次扩展路径长度最短的一个节点，并标记它，表示它的最短路已经被确定，之后不会再对它进行扩展。
流程如下（设 \(1\) 号点为起点，点 \(x\) 到点 \(1\) 的最短路为 \(d_x\)）：
- 初始化 \(d_1=0\)，其他节点的 \(d\) 值设为无限大。
- 找出一个未被标记的，\(d_x\) 值最小的节点 \(x\)，然后标记 \(x\)。
- 扫描节点 \(x\) 的所有出边 \((x,y,z)\)，如果 \(d_x+z
- 重复上述 \(2，3\) 两个步骤，直到所有节点都被标记。
不难发现，上述算法时间复杂度是 \(O(n^2)\) 的，而制约运行时间的关键是第二步，如果我们能想办法，在 \(o(\log n)\) 的时间内就找出最小的 \(d_x\) 值，时间复杂度就可以下降很多。那么我们很自然就能想到堆来优化，这样一来，时间复杂度就变为\(O(m \log n)\)，就好了很多。
流程分析：
作者暂时没有时间，以后会进行详细说明并配图
模板
以洛谷P4779 【模板】单源最短路径（标准版）为例：
这道题就是一道单纯的求单源最短路的板子题，只需要把用堆优化的 \(dijkstra\) 板子套上去就行，代码如下：
#include
#define maxn 100005
using namespace std;
int ver[maxn*2],val[maxn*2],next[maxn*2],head[maxn*2],d[maxn],tot;
bool v[maxn];
void add(int x,int y,int z){
ver[++tot]=y;val[tot]=z;next[tot]=head[x];head[x]=tot;
}
void dijkstra(int s){
memset(d,0x3f,sizeof(d));
priority_queue< pair >q;
d[s]=0;
q.push(make_pair(-d[s],s));
while(!q.empty()){
int x=q.top().second;
q.pop();
if(v[x])continue;
v[x]=1;
for(int i=head[x];i;i=next[i]){
int y=ver[i],z=val[i];
if(d[y]>d[x]+z){
d[y]=d[x]+z;
q.push(make_pair(-d[y],y));
}
}
}
}
int main(){
int n,m,s;
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=m;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
}
dijkstra(1);
for(int i=1;i<=n;i++)
printf("%d ",d[i]);
return 0;
}
时空复杂度分析：
上文已有提及，这里不做赘述。
用途分析：
\(dijkstra\) 在最短路方面有较广泛的应用，很多单纯的最短路问题可以用它解决，最短路问题和其他类型问题的混合也可以用它解决，比如：
- P6770 [USACO05MAR]Checking an Alibi 不在场的证明
最短路水题，毫无技术含量 - P1462 通往奥格瑞玛的道路
二分加 \(dijkstra\) - P1027 [NOIP2001 提高组] Car 的旅行路线
几何加 \(dijkstra\)
优缺点分析：
\(dijkstra\) 相比 \(SPFA\) 来说不那么容易被卡，复杂度也比 \(floyd\) 要优秀，所以笔者是比较推荐使用 \(dijkstra\) 来解决最短路问题的。
虽然 \(dijkstra\) 有着一些好处，但是它只适用于所有边的长度都是非负数的图。因为只有在边权都是非负数时，全局最小值才不可能被其他节点更新，所以已确定的最短路才不会再被更新，而最后得出来的结果也是对的。
那么对 \(dijkstra\) 的分析就先进行到这里，待笔者对其进行更深入的研究后再进行更新。