你可以创建一个Graph的实例,给定图的大小和各个节点之间的距离,然后调用dijkstra方法,传入源节点的编号,即可输出从源节点到各个节点的最短路径长度。
时间: 2024-02-24 09:59:17 浏览: 22
好的,我可以创建一个Graph的实例,给定图的大小和各个节点之间的距离,然后调用dijkstra方法,传入源节点的编号,即可输出从源节点到各个节点的最短路径长度。以下是一个简单的示例代码:
```python
import heapq
class Graph:
def __init__(self, n):
self.n = n
self.adj = [[] for _ in range(n)]
def add_edge(self, u, v, w):
self.adj[u].append((v, w))
self.adj[v].append((u, w))
def dijkstra(self, src):
dist = [float('inf')] * self.n
dist[src] = 0
pq = [(0, src)]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue
for v, w in self.adj[u]:
if dist[v] > dist[u] + w:
dist[v] = dist[u] + w
heapq.heappush(pq, (dist[v], v))
return dist
```
示例用法:
```python
g = Graph(5)
g.add_edge(0, 1, 2)
g.add_edge(0, 2, 5)
g.add_edge(1, 2, 1)
g.add_edge(1, 3, 3)
g.add_edge(2, 3, 2)
g.add_edge(2, 4, 3)
g.add_edge(3, 4, 1)
dist = g.dijkstra(0)
print(dist)
```
输出:
```
[0, 2, 3, 5, 6]
```
其中 `dist` 数组表示从源节点到各个节点的最短路径长度,例如 `dist[3]` 表示从源节点到节点 3 的最短路径长度为 5。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)