1. let G=(V,E) be an undirected weighted graph, and let T be the shortest path
spanning tree rooted at a vertex v. Suppose now that all the edge weights in G
are increased by a constant number c. Is T still the shortest path spanning
tree from v ?
网络上的解答说: Yes, 当用Dijkstra时都是选最小的edge加到shortest path, 故选到
的edge仍相同
可是我觉得怪怪的 不是提到Johnson的reweighting都会介绍每条edge增加固定的值
最短路径会跟着改变 因为path上的edge数不一样 这样这题应该是No吧?
2. Can we modify Dijkstra's algorithm to solve the single source longest path
problem by changing minimum to maximum?
网络上的解答说: Yes, 把relax的小于改成大于
可是我找到一个反例:
1 1
B

Q2 A->D = MAX{A->D, A->B->D, A->C->D, A->E->D}所以是没问题的

1是NO 例如三个点三条边 (s,t)=3 (s,x)=1 (x,t)=1各加100后，s到t的最短路径就变了2是NO single source longest path 类似于 hamilton path是个 NP-Complete 问题 除非给定的graph是dag才能这样解

soga~