求以下问题代码:给定邻接矩阵表示的带权有向图,其中每条边的权都是非负整数,并以-1代表不连通。给定图中的一个顶点V,称为源点。现在要计算从源到所有其它各顶点的最短路长度。输入为一行整数,以单一空格隔开,最后一个整数的后面无空格。输入时第1个数n为节点总数,第2个数至第n^2+1个数为邻接矩阵,以行优先方式存储(即:第2至第n+1个数为矩阵第一行,以此类推)第n^2+2个数为源点编号,节点编号从0开始。输出时一行共n−1个数,以单一空格隔开,依次代表源点到除源点外的各个节点的最短路径。最后一个数后面无空格,无换行、回车符。
时间: 2024-02-11 11:06:00 浏览: 89
好的,以下是基于Python语言的代码实现:
```python
import sys
# 读入输入数据
n = int(input())
inf = float('inf')
adj_matrix = [list(map(int, input().split())) for _ in range(n)]
src = int(input())
# 初始化dist和visited数组
dist = [inf] * n
visited = [False] * n
dist[src] = 0
# 主循环:重复执行n次
for _ in range(n):
# 从未访问过的节点中选取dist值最小的节点u
min_dist = inf
u = -1
for i in range(n):
if not visited[i] and dist[i] < min_dist:
min_dist = dist[i]
u = i
if u == -1:
break
visited[u] = True
# 对于所有与节点u相邻的节点v,更新dist[v]的值
for v in range(n):
if adj_matrix[u][v] != -1 and not visited[v]:
new_dist = dist[u] + adj_matrix[u][v]
if new_dist < dist[v]:
dist[v] = new_dist
# 输出结果
print(' '.join(str(dist[i]) for i in range(n) if i != src))
```
注意,在实现过程中我们使用了一个inf常量来表示正无穷,因为Python中没有类似C++和Java中INT_MAX或者Integer.MAX_VALUE这样的常量。另外,由于题目要求输出结果时最后一个数后面无空格、无换行符,因此我们使用了join方法来将数组中的元素连接成一个字符串输出。
阅读全文