線性陣列節點隨機鏈接到陣列中的其他節點，最短路徑

Question

信息： 我有一個由100個節點組成的陣列[0 .. 99]。每個節點都可以有鏈接的節點的任意數量：

EG1，0鏈接至5，10，15，20 EG2，1個鏈路到30，40，50 EG3等。

所有100個節點至少有一個鏈接節點，節點不知道誰鏈接到它們。

問題： 如何獲得如果提供START和END的最短鏈接路徑。

例如。 START = 5，END = 80，鏈接路徑（示例）：[5] - > 10-> 24-> 36 - > [80]？

我使用Pascal和/或PHP，但瞭解我在找什麼[代碼也有幫助]。

Answer 1

大量閱讀/算法： Shortest path problem。你實際上只是擁有同樣重要的每一個邊緣（就像你稱之爲「鏈接」）。

Answer 2

這是樹/圖還是森林？如果它是森林，則路徑可能無法一直定義。如果這是一個樹/圖，請嘗試使用廣度優先搜索。

想想這樣：比如說，你在隱祕的任務中尋找可愛的小雞在你的鄰居。你從自己的家開始，並將其標記爲START。接下來你會去敲你最近的鄰居吧？因此，我們將這樣做 - 將所有連接到隊列開始的節點都推送到隊列中。現在，重複搜索此隊列中所有節點的鄰居。並繼續這樣做，直到你得到你的女孩，呃，結束。

Answer 3

執行從Start節點開始的廣度優先遍歷，並在找到最終節點後立即退出。

Answer 4

這是否有周期？即它是一個DAG？

如果不存在週期：

List<Node> GetShortestPath(Node startNode, Node endNode) 
    { 
     //If this is the node you are looking for... 
     if (startNode.ReferenceEquals(endNode)) 
     { 
      //return a list with just the end node 
      List<Nodes> result = new List<Nodes>(); 
      result.Add(endNode);    
      return result; 
     } 

     List<Node> bestPath = null; 

     foreach(Node child in startNode.Children) 
     {    
      //get the shortest path from this child 
      List<Node> childPath = GetShortestPath(child, endNode); 
      if (childPath != null && 
      (bestPath == null || childPath.Count < bestPath.Count)) 
      { 
       bestPath = childPath; 
      } 
     } 

     bestPath.Insert(0, startNode); 
     return bestPath; 
    } 

[編輯：添加了一個示例的循環] 如果可存在週期：

List<Node> GetShortestPath(Node startNode, Node endNode) 
    { 
     List<Node> nodesToExclude = new List<Node>(); 
     return GetShortestPath(startNode, endNOde, nodesToExclude); 
    } 

    List<Node> GetShortestPath(Node startNode, Node endNode, List<Node> nodesToExclude) 
    { 
     nodesToExclude.Add(startNode); 

     List<Node> bestPath = null; 

     //If this is end node... 
     if (startNode.ReferenceEquals(endNode)) 
     { 
      //return a list with just the child node 
      List<Nodes> result = new List<Nodes>(); 
      result.Add(endNode);    
      return result; 
     } 

     foreach(Node child in startNode.Children) 
     { 
      if (!nodesToExclude.Contains(child)) 
      { 
       //get the shortest path from this child 
       List<Node> childPath = GetShortestPath(child, endNode); 
       if (childPath != null && 
       (bestPath == null || childPath.Count < bestPath.Count)) 
       { 
        bestPath = childPath; 
       } 
      } 
     } 

     nodesToExclude.Remove(startNode); 
     bestPath.Insert(0, child); 

     return bestPath; 
    } 

Answer 5

兩種結構：一組和列表。

在該集合中，存儲已經訪問過的節點。這會阻止您遵循循環。

該列表是包含以下對象的列表：（1）節點，以及（2）返回到找到它的節點的指針。

從開始節點開始，將它添加到集合中，用空回引用將它添加到列表中，然後將其可以到達列表的所有節點添加到列表中對索引0的反向引用（起始節點）。

然後其後列表中的每個元素，直到你到達終點，請執行下列操作：

1. 如果是在設定已經跳過它（你已經訪問過它），並移動到列表中的下一項。
2. 否則，將其添加到該集合中，並將其可以到達的所有節點添加到列表的末尾，並將反向引用添加到您正在查看的索引中。然後轉到列表中的下一個索引並重復。

如果您在任何時候到達終端節點（最好是因爲您將它添加到列表中 - 而不是在列表中訪問它），請通過對起始節點的反向引用進行跟蹤並將反轉路徑。

實施例：

鑑於節點0至3，其中
NODE0 - >節點1
NODE0 - >節點2
節點1 - >節點2
節點2 - >節點3
和NODE0是START和節點3是END

SET = {}
LIST = []

步驟1 - 添加STAR T：

SET = {NODE0}
LIST = [[NODE0，空]]

步驟2 - 在該列表的索引0 - 添加可達節點：

SET = {NODE0 ，節點1，節點2}
LIST = [[NODE0，空]，[節點1，0]，[節點2，0]]

步驟3 - 在該列表的索引1 - 添加可達節點：

node2已經在SET中。跳過將可達節點添加到LIST。
SET = {NODE0，節點1，節點2}
LIST = [[NODE0，空]，[節點1，0]，[節點2，0]]

步驟4 - 在索引2列表 - 添加可達節點：

SET = {NODE0，節點1，節點2，節點3}
LIST = [[NODE0，空]，[節點1，0]，[節點2，0]，[節點3，2 ]]

第5步 - 到達END，no w回溯：

插入到列表中的END節點（node3）對列表中的索引2具有反向引用，該索引是node2。這對列表中的索引0有一個反向引用，即node0（START）。反轉這一點，你會得到node0 - > node2 - > node3的最短路徑。