Dijkstra算法如何應用於一個程序中的無向和有向算法？

Question

該圖被表示在以下格式：

MAX 12 
NODE 1 1 
NODE 2 2 
NODE 3 3 
NODE 4 4 
NODE 5 5 
NODE 6 6 
NODE 7 7 
NODE 9 9 
NODE 8 8 
NODE 10 10 
NODE 11 11 
NODE 12 12 
EDGE 1 2 
EDGE 2 3 
EDGE 3 4 
EDGE 4 5 
EDGE 5 6 
EDGE 6 7 
EDGE 7 8 
EDGE 8 9 
EDGE 9 10 
EDGE 10 11 
EDGE 11 12 
EDGE 1 12 
EDGE 1 3 
EDGE 1 4 
EDGE 1 6 
EDGE 1 8 
EDGE 1 11 
EDGE 1 10 
EDGE 6 10 
EDGE 3 6 
EDGE 4 6 
EDGE 5 7 
EDGE 9 11 

我需要使用相鄰的列表中的那些邊緣閱讀。但是如果我想將它用作無向圖，那就是忽略所有邊的直接性。我怎麼知道每對節點的連通性？例如，在無向圖中（NODE 2，NODE 8）之間的最短距離是2（2-> 1> 8），但是對該圖使用Dijkstra算法得到4（2→3→8） 6-> 7-> 8）。我怎麼能代表無向圖，同時仍然使用相同的技術來讀取邊緣？

Answer 1

如果你真的不想改變在邊緣閱讀的技巧，你必須遍歷所有其他節點，看看你的節點是否在鄰接列表中而不是其他方式。

這會增加你的運行時間，但不會節省你太多的存儲空間，所以我建議只改變邊緣閱讀技巧。