複雜的C＃Linq算法

Question

我有一個C＃問題需要解決。我正在創建一個可以確定最短路徑的應用程序。有一個港口網絡，該方法需要制定出最快的路線。

我已經得到了這個與我的方法，但它似乎我重複的代碼和可能的路線可以永遠持續下去。有沒有人有一個更好的方式來測試所有可能的旅程，所以我能夠計算最短的一個想法？

public int ShortestJourneyTime(string startPort, string endPort) 
    { 
     int shortJourneyTime = 0; 
     var possStartRoutes = RouteData.Where(p => p.Key[0] == startPort); 

     if (possStartRoutes.Count() <= 0) 
      throw new InvalidOperationException(string.Format("{0} : Start port is invalid", startPort)); 

     foreach (var p in possStartRoutes) 
     { 
      int currentJourneyTime = p.Value; 

      var possRoutes2 = RouteData.Where(p2 => p2.Key[0] == p.Key[1]); 

      foreach (var p2 in possRoutes2) 
      { 
       if (p2.Key[1] == endPort) 
       { 
        currentJourneyTime += p2.Value; 
        if (shortJourneyTime > currentJourneyTime || shortJourneyTime == 0) 
         shortJourneyTime = currentJourneyTime; 
       } 
       else 
       { 
        var possRoutes3 = RouteData.Where(p3 => p3.Key[0] == p2.Key[1]); 
       } 
      } 
     } 

     return shortJourneyTime; 
    } 

端口數據存儲像下面

Dictionary<List<string>, int> testData = new Dictionary<List<string>, int>(); 

     List<string> routeOne = new List<string>() { "Buenos Aires", "New York" }; 
     testData.Add(routeOne, 6); 

Answer 1

隨着人們建議Dijkstra算法。這是您需要的算法。我保留了你的數據結構Dictionary<List<string>, int>，所以你仍然可以使用它。但是我改變了算法內部的數據結構並選擇了更合適的數據結構來使算法更容易。

這個想法是從開始到結束獲得所有可能的路徑。然後以最短路徑作爲結果。請注意，傳遞的路徑不應該重複意味着如果我們通過New York我們不應該再次通過它，否則我們陷入無限循環。

此方法的返回類型爲Tuple<List<string>, int>。其中List<string>是按順序持有端口的最短路徑，int是此路徑的長度。您可以使用屬性Item1和Item2訪問它們。

例如從Buenos Aires到Liverpool的最短路徑是字符串"Buenos Aires","Casablanca","Liverpool"的長度爲8天的最短路徑。

請注意，如果找不到任何內容，則此方法返回null。如果你願意，你可以拋出異常。只是取消了我評論的地方throw expetion

此方法的路徑類型爲Tuple<string, string, int>。 Item1是開始端口。 Item2是端口，Item3是這兩個端口之間的長度。

public Tuple<List<string>, int> TakeShortestJourney(string startPort, string endPort) 
{ 
    if (startPort == endPort) // just for special case when user puts same start and end port. 
    { 
     return new Tuple<List<string>, int>(new List<string>(){startPort}, 0); 
    } 

    // convert from Dictionary<List<string>, int> into List<Tuple<string, string, int>> 
    var t = RouteData.Select(x => new Tuple<string, string, int>(x.Key[0], x.Key[1], x.Value)); 
    var allPaths = new List<Tuple<string, string, int>>(t); 

    // This will hold all possible short paths. 
    var passedPaths = new List<Tuple<List<string>, int>>(); 

    // create a recursion method to do the search and fill the passedPaths. 
    Action<List<string>, string, int> getPath = null; 
    getPath = (list, start, length) => 
    { 
     list.Add(start); 

     foreach (
      var currentRoad in 
       allPaths.Where(x => !list.Contains(x.Item2) && x.Item1 == start).OrderBy(x => x.Item3)) 
     { 
      int newLength = length + currentRoad.Item3; // calculate new length. 

      if (currentRoad.Item2 == endPort) 
      { 
       list.Add(currentRoad.Item2); 
       passedPaths.Add(new Tuple<List<string>, int>(list, newLength)); 
       break; 
      } 

      if (passedPaths.Any(x => x.Item2 < newLength)) break; 

      getPath(new List<string>(list), currentRoad.Item2, newLength); 
     } 
    }; 

    // start search with initial empty list and 0 length. start from startPort 
    getPath(new List<string>(), startPort, 0); 

    // Take the shortest path from passed paths. 
    var shortestPath = passedPaths.OrderBy(x=> x.Item2).FirstOrDefault(); 

    if (shortestPath == null) { 
    // throw new ApplicationException("nothing was found"); 
    } 

    return shortestPath; 
} 

以下是如何使用此方法的示例。

var shortestPath = TakeShortestJourney("Buenos Aires", "Liverpool"); 

foreach (var p in shortestPath.Item1) // Item1 holds path 
{ 
    Console.WriteLine(p); 
} 

Console.WriteLine(shortestPath.Item2); // Item2 holds length 

關於遞歸操作：

list.Add(start); 

我們這樣做是爲每個調用，所以我們建立我們的路徑與秩序。

allPaths.Where(x => !list.Contains(x.Item2) && x.Item1 == start).OrderBy(x => x.Item3) 

此查詢將得到與start這是以前的路徑（x.Item1 == start）的月底開始的路徑，但它不會採取已經在我們列表中存在的路徑，以避免重複（!list.Contains(x.Item2)）。最後它會按Item3（長度）排序，所以我們選擇最短的（OrderBy(x => x.Item3)）。

if (currentRoad.Item2 == endPort) 
{ 
    list.Add(currentRoad.Item2); 
    passedPaths.Add(new Tuple<List<string>, int>(list, newLength)); 
    break; 
} 

這將檢查我們的路徑結束。當Item2（當前路徑結束）等於結束端口時發生。最後，我們將最後一項（Item2）添加到列表中，我們將我們的列表和最終長度一起保存在passedPaths之內。我們打破了循環，因爲我們知道這條路徑的長度會更長，因爲我們已經達到了最終的目的，所以不必爲其他路徑繼續。 （請記住，我們通過Item3命令他們）

if (passedPaths.Any(x => x.Item2 < newLength)) break; 

這一次僅僅是因爲如果有任何完整路徑存在，當前路徑的長度比大，停止由於沒有建立這條道路進一步優化意味着較短的路徑存在。也因爲查詢是有序的，所以下一個項目的長度更長，所以我們只是從這個路徑返回。基於RouteData，這可能會增加或降低性能。您可以安全地移除此部分而不影響結果。

getPath(new List<string>(list), currentRoad.Item2, newLength); 

這是算法的核心！遞歸調用。第一個參數是我們正在製作的list，但是我們每次都創建它的新參考，所以列表保持不受遞歸影響，我們可以繼續在我們的foreach循環中。第二個參數currentRoad.Item2是當前路徑的結尾，它將成爲下一條路徑的開始。最後一個參數newLength，當我們在Tuple<List<string>, int>中保存最終路徑時，我們需要這個參數。