Question

用dijkstra算法求出最短路径，从1到5，问：最短路径是50还是100？（并说明过程及原因）

如果是无向图的话又怎么样呢？回答好的话再加分

Answer 1

这个算法是用在无向图中的，这是个有向图，不适用的。

追问

那如果是无向图的话是什么呢？

追答

抱歉，是可以用在有向图中的。我仔细分析了一下，还是50。

追问

能说明原因吗

追答

因为不好写出来，所以简答说一下吧，就说一下被选节点放入集合S的顺序：1为原点；S集先选出了2，记录距离为10；又选出了4，记录距离为20；又选出了5，记录距离为50；又选出了3，记录距离为60。所以最短路径为50。

追问

那2和4总该有一个先进入集合s吧，如果2排在4前面进入s集合即按顺序，最短路径还是50吗？能把进入s集合顺序写一下吗？

追答

顺序就是上面说的顺序，2、4、5、3。