题目内容
(请给出正确答案)
[单选题]
在一个含有n个顶点的连通图中,任意一条简单路径的长度都不可能超过()
A.是无向图
B.是有向图
C.有奇数个顶点
D.有偶数个顶点
如搜索结果不匹配,请 联系老师 获取答案
A.是无向图
B.是有向图
C.有奇数个顶点
D.有偶数个顶点
第1题
第10题
算法5-6:迪杰斯特拉最短路径算法【图】 Description 在带权有向图G中,给定一个源点v,求从v到G中的其余各顶点的最短路径问题,叫做单源点的最短路径问题。 在常用的单源点最短路径算法中,迪杰斯特拉算法是最为常用的一种,是一种按照路径长度递增的次序产生最短路径的算法。 在本题中,读入一个有向图的带权邻接矩阵(即数组表示),建立有向图并按照以上描述中的算法求出源点至每一个其它顶点的最短路径长度。 Input 输入的第一行包含2个正整数n和s,表示图中共有n个顶点,且源点为s。其中n不超过50,s小于n。 以后的n行中每行有n个用空格隔开的整数。对于第i行的第j个整数,如果大于0,则表示第i个顶点有指向第j个顶点的有向边,且权值为对应的整数值;如果这个整数为0,则表示没有i指向j的有向边。当i和j相等的时候,保证对应的整数为0。 Output 只有一行,共有n-1个整数,表示源点至其它每一个顶点的最短路径长度。如果不存在从源点至相应顶点的路径,输出-1。 请注意行尾输出换行。 Sample Input4 1 0 3 0 1 0 0 4 0 2 0 0 0 0 0 1 0Sample Output6 4 7
为了保护您的账号安全,请在“上学吧”公众号进行验证,点击“官网服务”-“账号验证”后输入验证码“”完成验证,验证成功后方可继续查看答案!