Dijkstra 算法是一种用于计算带权有向图中单源最短路径（SSSP：Single-Source Shortest Path）的算法，由计算机科学家 Edsger Dijkstra 于 1956 年构思并于 1959 年发表。其解决的问题是：给定图 G 和源顶点 v，找到从 v 至图中所有顶点的最短路径。
Dijkstra 算法采用贪心算法（Greedy Algorithm）范式进行设计。在最短路径问题中，对于带权有向图 G = (V, E)，Dijkstra 算法的初始实现版本未使用最小优先队列实现，其时间复杂度为 O(V2)，基于 Fibonacci heap 的最小优先队列实现版本，其时间复杂度为 O(E + VlogV)。
Bellman-Ford 算法和 Dijkstra 算法同为解决单源最短路径的算法。对于带权有向图 G = (V, E)，Dijkstra 算法要求图 G 中边的权值均为非负，而 Bellman-Ford 算法能适应一般的情况（即存在负权边的情况）。一个实现的很好的 Dijkstra 算法比 Bellman-Ford 算法的运行时间 O(V*E) 要低。
Dijkstra 算法描述：
- 创建源顶点 v 到图中所有顶点的距离的集合 distSet，为图中的所有顶点指定一个距离值，初始均为 Infinite，源顶点距离为 0；
- 创建 SPT（Shortest Path Tree）集合 sptSet，用于存放包含在 SPT 中的顶点；
- 如果 sptSet 中并没有包含所有的顶点，则：
- 选中不包含在 sptSet 中的顶点 u，u 为当前 sptSet 中未确认的最短距离顶点；
- 将 u 包含进 sptSet；
- 更新 u 的所有邻接顶点的距离值；
伪码实现如下：
function Dijkstra(Graph, source):
dist[source] ← // Distance from source to source
prev[source] ← undefined // Previous node in optimal path initialization
for each vertex v in Graph: // Initialization
if v ≠ source // Where v has not yet been removed from Q (unvisited nodes)
dist[v] ← infinity // Unknown distance function from source to v
prev[v] ← undefined // Previous node in optimal path from source
end if
add v to Q // All nodes initially in Q (unvisited nodes)
end for
while Q is not empty:
u ← vertex in Q with min dist[u] // Source node in first case
remove u from Q
for each neighbor v of u: // where v has not yet been removed from Q.
alt ← dist[u] + length(u, v)
if alt < dist[v]: // A shorter path to v has been found
dist[v] ← alt
prev[v] ← u
end if
end for
end while
return dist[], prev[]
end function
例如，下面是一个包含 9 个顶点的图，每条边分别标识了距离。
源顶点 source = 0，初始时，
- sptSet = {false, false, false, false, false, false, false, false, false};
- distSet = {0, INF, INF, INF, INF, INF, INF, INF, INF};
将 0 包含至 sptSet 中；
- sptSet = {true, false, false, false, false, false, false, false, false};
更新 0 至其邻接节点的距离；
- distSet = {0, 4, INF, INF, INF, INF, INF, 8, INF};
选择不在 sptSet 中的 Min Distance 的顶点，为顶点 1，则将 1 包含至 sptSet；
- sptSet = {true, true, false, false, false, false, false, false, false};
更新 1 至其邻接节点的距离；
- distSet = {0, 4, 12, INF, INF, INF, INF, 8, INF};
选择不在 sptSet 中的 Min Distance 的顶点，为顶点 7，则将 7 包含至 sptSet；
- sptSet = {true, true, false, false, false, false, false, true, false};
更新 7 至其邻接节点的距离；
- distSet = {0, 4, 12, INF, INF, INF, 9, 8, 15};
选择不在 sptSet 中的 Min Distance 的顶点，为顶点 6，则将 6 包含至 sptSet；
- sptSet = {true, true, false, false, false, false, true, true, false};
更新 6 至其邻接节点的距离；
- distSet = {0, 4, 12, INF, INF, 11, 9, 8, 15};
以此类推，直到遍历结束。
- sptSet = {true, true, true, true, true, true, true, true, true};
- distSet = {0, 4, 12, 19, 21, 11, 9, 8, 14};
最终结果为源顶点 0 至所有顶点的距离：
Vertex Distance from Source
0 0
1 4
2 12
3 19
4 21
5 11
6 9
7 8
8 14
C#代码实现：
using System;
using System.Collections.Generic;
using System.Linq; namespace GraphAlgorithmTesting
{
class Program
{
static void Main(string[] args)
{
int[,] graph = new int[, ]
{
{, , , , , , , , },
{, , , , , , , , },
{, , , , , , , , },
{, , , , , , , , },
{, , , , , , , , },
{, , , , , , , , },
{, , , , , , , , },
{, , , , , , , , },
{, , , , , , , , }
}; Graph g = new Graph(graph.GetLength());
for (int i = ; i < graph.GetLength(); i++)
{
for (int j = ; j < graph.GetLength(); j++)
{
if (graph[i, j] > )
g.AddEdge(i, j, graph[i, j]);
}
} int[] dist = g.Dijkstra();
Console.WriteLine("Vertex\t\tDistance from Source");
for (int i = ; i < dist.Length; i++)
{
Console.WriteLine("{0}\t\t{1}", i, dist[i]);
} Console.ReadKey();
} class Edge
{
public Edge(int begin, int end, int distance)
{
this.Begin = begin;
this.End = end;
this.Distance = distance;
} public int Begin { get; private set; }
public int End { get; private set; }
public int Distance { get; private set; }
} class Graph
{
private Dictionary<int, List<Edge>> _adjacentEdges
= new Dictionary<int, List<Edge>>(); public Graph(int vertexCount)
{
this.VertexCount = vertexCount;
} public int VertexCount { get; private set; } public void AddEdge(int begin, int end, int distance)
{
if (!_adjacentEdges.ContainsKey(begin))
{
var edges = new List<Edge>();
_adjacentEdges.Add(begin, edges);
} _adjacentEdges[begin].Add(new Edge(begin, end, distance));
} public int[] Dijkstra(int source)
{
// dist[i] will hold the shortest distance from source to i
int[] distSet = new int[VertexCount]; // sptSet[i] will true if vertex i is included in shortest
// path tree or shortest distance from source to i is finalized
bool[] sptSet = new bool[VertexCount]; // initialize all distances as INFINITE and stpSet[] as false
for (int i = ; i < VertexCount; i++)
{
distSet[i] = int.MaxValue;
sptSet[i] = false;
} // distance of source vertex from itself is always 0
distSet[source] = ; // find shortest path for all vertices
for (int i = ; i < VertexCount - ; i++)
{
// pick the minimum distance vertex from the set of vertices not
// yet processed. u is always equal to source in first iteration.
int u = CalculateMinDistance(distSet, sptSet); // mark the picked vertex as processed
sptSet[u] = true; // update dist value of the adjacent vertices of the picked vertex.
for (int v = ; v < VertexCount; v++)
{
// update dist[v] only if is not in sptSet, there is an edge from
// u to v, and total weight of path from source to v through u is
// smaller than current value of dist[v]
if (!sptSet[v]
&& distSet[u] != int.MaxValue
&& _adjacentEdges[u].Exists(e => e.End == v))
{
int d = _adjacentEdges[u].Single(e => e.End == v).Distance;
if (distSet[u] + d < distSet[v])
{
distSet[v] = distSet[u] + d;
}
}
}
} return distSet;
} /// <summary>
/// A utility function to find the vertex with minimum distance value,
/// from the set of vertices not yet included in shortest path tree
/// </summary>
private int CalculateMinDistance(int[] distSet, bool[] sptSet)
{
int minDistance = int.MaxValue;
int minDistanceIndex = -; for (int v = ; v < VertexCount; v++)
{
if (!sptSet[v] && distSet[v] <= minDistance)
{
minDistance = distSet[v];
minDistanceIndex = v;
}
} return minDistanceIndex;
}
}
}
}
参考资料
- 广度优先搜索
- Dijkstra's algorithm
- Greedy Algorithms | Set 7 (Dijkstra’s shortest path algorithm)
- Bellman-Ford 单源最短路径算法
- Introduction to Algorithms 6.006 - Lecture 16
本篇文章《Dijkstra 单源最短路径算法》由 Dennis Gao 发表自博客园，未经作者本人同意禁止任何形式的转载，任何自动或人为的爬虫转载行为均为耍流氓。