最短路径问题是图论研究中的一个经典算法问题, 旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。给定一个有向带权图,以及图中任意两个顶点,求两个顶点之间的最短路径。 约定: (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