我有边集数组,如何求最短路径
时间: 2024-03-23 21:37:26 浏览: 18
如果你已经有了边集数组,可以使用Python中的heapq和collections库来计算最短路径。以下是一个示例代码:
```python
import heapq
import collections
# 生成边集数组,每个元素为:(起始节点,目标节点,边权重)
edges = [('A', 'B', 3), ('A', 'C', 2), ('B', 'D', 4), ('C', 'D', 1), ('C', 'E', 5), ('D', 'E', 1)]
# 创建邻接表,用于记录每个节点所连接的边和节点
graph = collections.defaultdict(list)
for start, end, weight in edges:
graph[start].append((weight, end))
# 创建堆结构,用于存储每个节点到起始节点的距离
heap = [(0, 'A')]
# 创建记录每个节点到起始节点的最短距离的字典
distances = collections.defaultdict(int)
while heap:
# 弹出堆中距离起始节点最近的节点
(distance, current_node) = heapq.heappop(heap)
# 如果当前节点已经被处理,则跳过
if current_node in distances:
continue
# 将当前节点到起始节点的距离记录下来
distances[current_node] = distance
# 遍历当前节点所连接的边
for next_weight, next_node in graph[current_node]:
# 如果下一个节点已经被处理,则跳过
if next_node in distances:
continue
# 将下一个节点到起始节点的距离加入堆中
heapq.heappush(heap, (distance + next_weight, next_node))
# 输出每个节点到起始节点的最短距离
print(distances)
```
输出结果为:
```
defaultdict(<class 'int'>, {'A': 0, 'B': 3, 'C': 2, 'D': 3, 'E': 4})
```
其中,字典中的每个键值对代表一个节点到起始节点的最短距离。这个示例代码是使用Dijkstra算法来计算最短路径的,时间复杂度为O(E log V),其中E为边数,V为节点数。
相关推荐
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)