首页 > 试题广场 >

Newman教授觉得自己发现了Dijkstra算法的一一个更

[问答题]
Newman教授觉得自己发现了Dijkstra算法的一一个更简单的证明。  他声称Dijkstra算法对最短路径上面的每条边的松弛次序与该条边在该条最短路径中的次序相同,因此,路径松弛性质适用于从源结点可以到达的所有结点。请构造一个有向图来说明Dijkstra算法并不一定按照最短路径中边的出现次序来对边进行松弛,  从而证明教授是错的

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