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