用python实现最短路问题
时间: 2023-09-16 12:14:21 浏览: 51
最短路问题是指在一个加权有向图中找到从起点到终点的最短路径,其中边权表示路径长度。常见的解决算法有Dijkstra算法和Bellman-Ford算法。下面给出Python实现代码。
首先,我们需要定义一个表示图的类Graph,它包含节点数、边数和邻接表等属性和方法。在邻接表中,每个节点的所有邻居节点及对应的边权值都被存储在一个列表中。
```python
class Graph:
def __init__(self, num_vertices):
self.num_vertices = num_vertices
self.adjacency_list = [[] for _ in range(num_vertices)]
def add_edge(self, src, dest, weight):
self.adjacency_list[src].append((dest, weight))
```
接下来,我们实现Dijkstra算法。该算法维护一个set集合S和一个优先队列Q,其中S包含已经确定最短路径的节点,而Q中包含待处理的节点。首先,将起点加入S中,并将所有邻居节点加入Q中。然后,对于Q中的每个节点,计算它到起点的距离是否更短,如果更短,则更新距离并加入S中。最后,当Q为空时,算法结束,S中包含了所有最短路径经过的节点及它们到起点的距离。
```python
import heapq
def dijkstra(graph, start):
distances = [float('inf')] * graph.num_vertices
distances[start] = 0
pq = [(0, start)]
while len(pq) > 0:
curr_distance, curr_vertex = heapq.heappop(pq)
if curr_distance > distances[curr_vertex]:
continue
for neighbor, weight in graph.adjacency_list[curr_vertex]:
distance = curr_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(pq, (distance, neighbor))
return distances
```
最后,我们可以使用上述代码来解决最短路问题。例如,下面的代码创建了一个有向图,然后使用Dijkstra算法找到从起点0到终点4的最短路径。
```python
graph = Graph(5)
graph.add_edge(0, 1, 10)
graph.add_edge(0, 3, 5)
graph.add_edge(1, 2, 1)
graph.add_edge(1, 3, 2)
graph.add_edge(2, 4, 4)
graph.add_edge(3, 1, 3)
graph.add_edge(3, 2, 9)
graph.add_edge(3, 4, 2)
distances = dijkstra(graph, 0)
print(distances[4]) # 输出最短路径长度
```
输出结果为11,表示从起点0到终点4的最短路径长度为11。