首页 > 试题广场 >

对于一个权值大于0的带权有向图,采用Dijkstra算法求源

[问答题]

对于一个权值大于0的带权有向图,采用Dijkstra算法求源点v出发的最短路径,回答一下问题:

(1) S中存放已求出最短路径的顶点序列(依先后次序),若S的顶点序列为v 1 ,v 2 ,...,v k ,则从v到v i 的路径长度总是大于从v到v j (j<i)的路径长度吗?

(2) 对Dijkstra算法做这样的改动:每次都选取最远路径的顶点,其余不变,则这样改动后的算法能求从源点v到其余所有顶点的最长路径吗?

(3) 如果带权有向图中存在负权,采用Dijkstra算法能求出从源点v到其余顶点的最短路径吗?如果能求,请予以证明,如果不能求,请给出一个反例。

这道题你会答吗?花几分钟告诉大家答案吧!