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~