题库>> 1020-图-最短路径
最短路径问题是图论研究中的一个经典算法问题, 旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。给定一个有向带权图,以及图中任意两个顶点,求两个顶点之间的最短路径。
约定:
(1)使用邻接矩阵表示图
(2)顶点编号从0开始
(3)最短路径唯一
(4)若两个顶点没有直接相连,权重值设置为-1

例如:
矩阵A的邻接矩阵表示为:
-1, 3,-1, 2,-1
-1,-1, 1,-1,-1
-1,-1,-1,-1, 1
-1,-1,-1,-1, 4
-1,-1,-1,-1,-1

顶点0->4的最短路径:0,1,2,4
顶点4->0的最短路径(有向性):不存在,使用-1表示
输入、输出描述
输入:
A:有向图的邻接矩阵表示,若两个顶点没有直接相连,权重设置为-1
n:顶点的个数,顶点编号为:0,1,2...n-1
v1:起始顶点
v2:终点
输出:
从顶点v1到顶点v2之间的最短路径构成的数组,若不存在返回一个长度为1的数组,且元素值为-1
Example
输入:
A:
-1, 3,-1, 2,-1
-1,-1, 1,-1,-1
-1,-1,-1,-1, 1
-1,-1,-1,-1, 4
-1,-1,-1,-1,-1
n:5
v1:0
v2:4
输出:
0,1,2,4
"Ctr-Q":自动补全
欢迎加算法刷题交流QQ群:474397739,每周刷题比赛,精美礼品等你拿!
评论专区
分享本文 微信公众号