dijisktra方法python算法实现最短路径实例打印输出
时间: 2023-10-12 22:15:47 浏览: 44
好的,以下是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 print_solution(self, dist):
print("Vertex \t Distance from Source")
for node in range(self.V):
print(node, "\t\t", dist[node])
def min_distance(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.min_distance(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.print_solution(dist)
```
这是一个Graph类,其中包含了Dijkstra算法的实现。你可以创建一个Graph的实例,给定图的大小和各个节点之间的距离,然后调用`dijkstra`方法,传入源节点的编号,即可输出从源节点到各个节点的最短路径长度。