在加權圖中確定最佳路徑的算法

Question

這是我的測試練習題，我查了一下加權圖和一些相關材料，但被卡住了，所以需要一些想法來開始。

假設你想在節點s從你家到你的伴侶的 房子節點T在加權圖G =（V，E，W）。但是你想停止當地Fish'n 如果可能，芯片會放置在節點u上，而不會增加路徑長度的20％以上。

（a）描述一個有效的算法，如果你這樣做並不是過於昂貴，那麼它將決定一個最佳的s→t路徑。 （它要麼 返回從s到t的最短路徑或從到含有T U，有關情況取決於 的最短路徑。）你應該讓你的算法運行儘可能有效地

Answer 1

試試這個Dijkstra algorithm。找出從s到t，s到u和u到t的最短路徑。然後，在數學的幫助下（你可以看到你的答案）。乾杯。