Python 中的 Dijkstra 算法
Vaibhhav Khetarpal
2023年10月10日
Dijkstra 算法可以定义为一种贪婪算法，可用于找出从源顶点到加权图中存在的任何其他可能顶点的最短距离，前提是该顶点可从源顶点到达。
本教程讨论在 Python 中实现寻找最短路径的 Dijkstra 算法。
如上所述，Dijkstra 的算法是贪婪的。贪心算法可以定义为一种算法范式，它专注于为给定问题构建一个逐个解决方案，然后选择最有利的选项。
Dijkstra 算法的工作原理如下。
- 给定几个未访问的顶点，选择与源距离最小的顶点并访问它。
- 然后更新每个邻居的距离。对访问顶点也是如此，它的当前距离大于它们之间给定边的总和和权重。
- 需要重复步骤 1 和 2，直到没有未访问的顶点。
Dijkstra 算法与另一种贪婪算法 Prim 的最小生成树算法相似，因为它们都需要生成 SPT（最短路径树），以源为树的根。
以下代码使用 Dijkstra 算法在 Python 中寻找最短路径。
import sys
class Graph:
def __init__(self, vertx):
self.V = vertx
self.graph = [[0 for column in range(vertx)] for row in range(vertx)]
def pSol(self, dist):
print("Distance of vertex from source")
for node in range(self.V):
print(node, "t", dist[node])
def minDistance(self, dist, sptSet):
min = sys.maxsize
for v in range(self.V):
if dist[v] < min and sptSet[v] == False:
min = dist[v]
min_index = v
return min_index
def dijk(self, source):
dist = [sys.maxsize] * self.V
dist[source] = 0
sptSet = [False] * self.V
for cout in range(self.V):
u = self.minDistance(dist, sptSet)
sptSet[u] = True
for v in range(self.V):
if (
self.graph[u][v] > 0
and sptSet[v] == False
and dist[v] > dist[u] + self.graph[u][v]
):
dist[v] = dist[u] + self.graph[u][v]
self.pSol(dist)
f = Graph(9)
f.graph = [
[0, 4, 0, 0, 0, 0, 0, 8, 0],
[4, 0, 8, 0, 0, 0, 0, 11, 0],
[0, 8, 0, 7, 0, 4, 0, 0, 2],
[0, 0, 7, 0, 9, 14, 0, 0, 0],
[0, 0, 0, 9, 0, 10, 0, 0, 0],
[0, 0, 4, 14, 10, 0, 2, 0, 0],
[0, 0, 0, 0, 0, 2, 0, 1, 6],
[8, 11, 0, 0, 0, 0, 1, 0, 7],
[0, 0, 2, 0, 0, 0, 6, 7, 0],
]
f.dijk(0)
上面的代码提供了以下输出：
Distance of vertex from source
0 t 0
1 t 4
2 t 12
3 t 19
4 t 21
5 t 11
6 t 9
7 t 8
8 t 14
Dijkstra 的算法与深度优先搜索算法非常相似，尽管这两种算法并非完全出于同一目的而存在。
深度优先搜索和 Dijkstra 算法之间唯一的显着区别是前者的工作速度比后者慢，因为深度优先搜索 (DFS) 算法使用堆栈技术。另一方面，Dijkstra 的算法利用了相对较慢的堆技术。
Vaibhhav is an IT professional who has a strong-hold in Python programming and various projects under his belt. He has an eagerness to discover new things and is a quick learner.
LinkedIn