P大您好，可能我表達不夠完善@@ ╔═══╦═══╦═══╦═Ｄ═╗ ║　　　║　　　║　　　║　　　║ ║　　　║　　　║　　　║　　　║ ║　　　║　　　║　　　║　　　║ ╠═══╬═══╬═══╬═══╣ ║　　　║　　　║　　　║　　　║ ║　　　║　　　║　　　║　　　║ ║　　　║　　　║　　　║　　　║ ╠═══╬═══╬═══╬═══╣ ║　　　║　　　║　　　║　　　║ ║　　　○　　　║　　　║　　　║ ║　　　║　　　║　　　║　　　║ ╠Ｓ→→→═○═╬═══╬═══╣ ║　　　║　　　║　　　║　　　║ ║　　　Ｘ　　　║　　　║　　　║ ║　　　║　　　║　　　║　　　║ ╚═══╩═══╩═══╩═══╝ 假設現在由S走到D， 當在第一個路口的時候，我可以選擇○兩條路徑行走(最短路徑) 因此，此時會有兩種情境，暫定Case1和Case2 如果走Ｘ的話，則會繞遠路 　　　　　　　Case 1　　　　　　　　　　　　　　　　　Case 2 ╔═══╦═══╦═══╦═Ｄ═╗　　　╔═══╦═══╦═══╦═Ｄ═╗ ║　　　║　　　║　　　║　　　║　　　║　　　║　　　║　　　║　　　║ ║　　　║　　　║　　　║　　　║　　　║　　　║　　　║　　　║　　　║ ║　　　║　　　║　　　║　　　║　　　║　　　║　　　║　　　║　　　║ ╠═══╬═══╬═══╬═══╣　　　╠═══╬═══╬═══╬═══╣ ║　　　║　　　║　　　║　　　║　　　║　　　║　　　║　　　║　　　║ ║　　　○　　　║　　　║　　　║　　　║　　　║　　　║　　　║　　　║ ║　　　║　　　║　　　║　　　║　　　║　　　║　　　║　　　║　　　║ ╠═Ｘ═↑═○═╬═══╬═══╣　　　╠═══╬═══╬═══╬═══╣ ║　　　↑　　　║　　　║　　　║　　　║　　　║　　　║　　　║　　　║ ║　　　↑　　　║　　　║　　　║　　　║　　　║　　　○　　　║　　　║ ║　　　↑　　　║　　　║　　　║　　　║　　　║　　　║　　　║　　　║ ╠Ｓ→→↑═══╬═══╬═══╣　　　╠Ｓ→→→→→→→═○═╬═══╣ ║　　　║　　　║　　　║　　　║　　　║　　　║　　　║　　　║　　　║ ║　　　║　　　║　　　║　　　║　　　║　　　║　　　Ｘ　　　║　　　║ ║　　　║　　　║　　　║　　　║　　　║　　　║　　　║　　　║　　　║ ╚═══╩═══╩═══╩═══╝　　　╚═══╩═══╩═══╩═══╝ 在Case1這部分，到第二個路口時，又可以選擇往上或往右走 但是不能往左邊走，因為此時這樣就會變成繞遠路 在Case2這部分，到第二個路口時，也是可以選擇往上或往右走 但是不能往下走，因為往下走則會變成繞遠路 把問題簡單的來說，就是需要在每個路口判斷<=2條最短的路徑 因為其中一條會是繞遠路 ※ 引述《PsMonkey (痞子軍團團長)》之銘言： : ※ 引述《MrGG (頭有點痛)》之銘言： : : 請問一下，如果在街道型的Shortest Path 該如何解 (如下圖) : : ╔═══╦═══╦═══→→Ｄ═╗ : : ║　　　║　　　║　　　↑　　　║ : : ║　　　║　　　║　　　↑　　　║ : : ║　　　║　　　║　　　↑　　　║ : : ╠═══╬═══→→→→↑═══╣ : : ║　　　║　　　↑　　　║　　　║ : : ║　　　║　　　↑　　　║　　　║ : : ║　　　║　　　↑　　　║　　　║ : : ╠═══→→→→↑═══╬═══╣ : : ║　　　↑　　　║　　　║　　　║ : : ║　　　↑　　　║　　　║　　　║ : : ║　　　↑　　　║　　　║　　　║ : : ╠Ｓ→→↑═══╬═══╬═══╣ : : ║　　　║　　　║　　　║　　　║ : : ║　　　║　　　║　　　║　　　║ : : ║　　　║　　　║　　　║　　　║ : : ╚═══╩═══╩═══╩═══╝ : : 假設情境S→D，那麼箭頭所指向的是最短路徑 : 我先往東走到交會點，接著往北一直走到 D 的 y 座標，然後在往東走到 D : 這樣也是最短路徑.... （應該沒錯吧？） : 如果這樣的話，這個問題就... : 先一直走到 Dy - 1（或 +1） : 然後接著增加（或減少）x 座標，直到等於 Dx，然後再走到 D : （判斷括號內容也很簡單吧？） : ㄜ...... 抱歉，我不覺得這是個問題啊... 囧? : 還是我哪裡誤會 or 你有什麼前提沒有說清楚 : : 那麼如果以街道型的來規劃最短路徑，每條街區長度皆相同 : : 該如何去算出最短路徑? --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 218.175.197.82