那请你写一个dijkstra算法的代码,并且在最后以矩阵的形式呈现结果
时间: 2024-02-03 13:15:58 浏览: 24
好的,以下是一个简单的Dijkstra算法的Python代码,使用邻接矩阵作为图的表示方式:
```python
import sys
def dijkstra(graph, start):
n = len(graph)
visited = [False] * n
dist = [sys.maxsize] * n
dist[start] = 0
for i in range(n):
min_dist = sys.maxsize
u = -1
for j in range(n):
if not visited[j] and dist[j] < min_dist:
min_dist = dist[j]
u = j
visited[u] = True
for v in range(n):
if not visited[v] and graph[u][v] > 0 and dist[u] + graph[u][v] < dist[v]:
dist[v] = dist[u] + graph[u][v]
return dist
graph = [
[0, 7, 9, 0, 0, 14],
[7, 0, 10, 15, 0, 0],
[9, 10, 0, 11, 0, 2],
[0, 15, 11, 0, 6, 0],
[0, 0, 0, 6, 0, 9],
[14, 0, 2, 0, 9, 0]
]
start = 0
dist = dijkstra(graph, start)
print("最短路径:")
for i in range(len(dist)):
print("从节点", start, "到节点", i, "的距离为", dist[i])
print("矩阵形式:")
for row in graph:
print(row)
```
该代码使用了邻接矩阵表示图,其中graph[i][j]表示从节点i到节点j的距离,如果这两个节点之间没有边相连,则距离为0。start表示起始节点的编号。最后输出的结果有两部分,一部分是从起始节点到其他节点的最短距离,另一部分是邻接矩阵的形式,可以更直观地看到整个图的结构。
相关推荐
![py](https://img-home.csdnimg.cn/images/20210720083646.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)