迪杰斯特拉算法python代码
时间: 2023-07-23 13:09:37 浏览: 96
Python实现迪杰斯特拉算法并生成最短路径的示例代码
以下是迪杰斯特拉算法的 Python 代码:
```python
import sys
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = [[0 for column in range(vertices)]
for row in range(vertices)]
def printSolution(self, dist):
print("Vertex \t Distance from Source")
for node in range(self.V):
print(node, "\t\t", dist[node])
def minDistance(self, dist, sptSet):
min_dist = sys.maxsize
for v in range(self.V):
if dist[v] < min_dist and sptSet[v] == False:
min_dist = dist[v]
min_index = v
return min_index
def dijkstra(self, src):
dist = [sys.maxsize] * self.V
dist[src] = 0
sptSet = [False] * self.V
for i 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.printSolution(dist)
```
这是一个简单的实现,可以在一个带权有向图中找到从源节点到其他节点的最短路径。
阅读全文