Dijkstra算法python对于无向加权图打印最短路径
时间: 2023-07-11 12:10:18 浏览: 94
Python-Graphs:DFS,BFS,Dijkstra的单一来源最短路径
以下是使用Dijkstra算法在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, src):
print("Vertex \t Distance from Source")
for node in range(self.V):
print(node, "\t\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 dijkstra(self, src):
dist = [sys.maxsize] * self.V
dist[src] = 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.printSolution(dist, src)
```
在上面的代码中,我们首先定义了一个`Graph`类,其中`__init__`方法初始化了`V`个节点的图。然后,`printSolution`方法用于打印从源节点到每个节点的距离。`minDistance`方法用于找到距离源节点最近的未访问节点。最后,`dijkstra`方法使用Dijkstra算法找到从源节点到每个节点的最短路径,并打印结果。
阅读全文