编程实现图的单源点最短路径算法 Dijkstra(A,v),其中 A 是用邻接矩阵 表示的有向图图,v 是指定的起点,求从 v 出发到图中其它所有顶点的最短路径。
时间: 2024-02-06 07:12:34 浏览: 143
以下是 Python 代码实现 Dijkstra 算法:
```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, spt_set):
min_dist = sys.maxsize
for v in range(self.V):
if dist[v] < min_dist and spt_set[v] == False:
min_dist = dist[v]
min_index = v
return min_index
# 实现 Dijkstra 算法
def dijkstra(self, src):
dist = [sys.maxsize] * self.V
dist[src] = 0
spt_set = [False] * self.V
for cout in range(self.V):
u = self.min_distance(dist, spt_set)
spt_set[u] = True
for v in range(self.V):
if (self.graph[u][v] > 0 and
spt_set[v] == False and
dist[v] > dist[u] + self.graph[u][v]):
dist[v] = dist[u] + self.graph[u][v]
self.print_solution(dist)
# 测试代码
g = Graph(9)
g.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]]
g.dijkstra(0)
```
其中,我们定义了一个 Graph 类来表示图,它包含一个邻接矩阵 graph 和顶点数 V。dijkstra 方法接收一个起点 src,然后使用 Dijkstra 算法计算从起点到所有顶点的最短路径。最后,我们使用 print_solution 方法打印结果。
阅读全文