Dijkstra 单源最短路径算法

时间:2021-12-03 21:49:31

Dijkstra 算法是一种用于计算带权有向图中单源最短路径(SSSP:Single-Source Shortest Path)的算法,由计算机科学家 Edsger Dijkstra 于 1956 年构思并于 1959 年发表。其解决的问题是:给定图 G 和源顶点 v,找到从 v 至图中所有顶点的最短路径。

Dijkstra 单源最短路径算法

Dijkstra 算法采用贪心算法(Greedy Algorithm)范式进行设计。在最短路径问题中,对于带权有向图 G = (V, E),Dijkstra 算法的初始实现版本未使用最小优先队列实现,其时间复杂度为 O(V2),基于 Fibonacci heap 的最小优先队列实现版本,其时间复杂度为 O(E + VlogV)。

Dijkstra 单源最短路径算法

Bellman-Ford 算法和 Dijkstra 算法同为解决单源最短路径的算法。对于带权有向图 G = (V, E),Dijkstra 算法要求图 G 中边的权值均为非负,而 Bellman-Ford 算法能适应一般的情况(即存在负权边的情况)。一个实现的很好的 Dijkstra 算法比 Bellman-Ford 算法的运行时间 O(V*E) 要低。

Dijkstra 算法描述:

  1. 创建源顶点 v 到图中所有顶点的距离的集合 distSet,为图中的所有顶点指定一个距离值,初始均为 Infinite,源顶点距离为 0;
  2. 创建 SPT(Shortest Path Tree)集合 sptSet,用于存放包含在 SPT 中的顶点;
  3. 如果 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 个顶点的图,每条边分别标识了距离。

Dijkstra 单源最短路径算法

源顶点 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};

Dijkstra 单源最短路径算法

选择不在 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};

Dijkstra 单源最短路径算法

选择不在 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};

Dijkstra 单源最短路径算法

选择不在 sptSet 中的 Min Distance 的顶点,为顶点 6,则将 6 包含至 sptSet;

  • sptSet = {truetrue, false, false, false, false, truetrue, false};

更新 6 至其邻接节点的距离;

  • distSet = {0412, INF, INF, 119815};

Dijkstra 单源最短路径算法

以此类推,直到遍历结束。

  • sptSet = {truetrue, true, true, true, truetruetrue, true};
  • distSet = {0412, 19, 21119814};

Dijkstra 单源最短路径算法

最终结果为源顶点 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 单源最短路径算法》由 Dennis Gao 发表自博客园,未经作者本人同意禁止任何形式的转载,任何自动或人为的爬虫转载行为均为耍流氓。