最短路徑查找器

Question

比方說，我有以下CSV

Sydney,Dubai,1 
Dubai,Venice,2 
Venice,Rio,3 
Venice,Sydney,1 
Sydney,Rio,7 

第一場是From秒是To，三是Duration。

我需要的，可以採取From輸入和吐出的最短路徑的所有其他To場在以下格式 -

Selected City: Sydney 
To 1: Dubai, Smallest Path Length: 1, Path: Sydney, Dubai. 
To 2: Venice, Smallest Path Length: 3, Path: Sydney, Dubai, Venice. 
To 3: Rio, Smallest Path Length: 6, Path: Sydney, Dubai, Venice, Rio. 

(N.B. Sydney-Rio is 7 hours long hence Sydney-Dubai-Venice-Rio 
is the shortest route here which takes 2 hours). 

我沒有任何代碼在這裏添加加上其他人有方法建議使用Dijkstra的算法，但到目前爲止我還沒有一個例子能夠完成我所需要的。

Answer 1

我寫滿足您的需要一個小的控制檯程序。這是非常基本的，如果需要可以進一步增強。

如果你需要一個可下載的解決方案，請讓我知道。

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 
using System.Threading.Tasks; 

namespace ShortPath 

{ 
    class Program 
    { 
     static void Main(string[] args) 
     { 
// assuming you have loaded your CSVs into a list of string 
      List<string> csvLines = new List<string>() 
      { 
       "Sydney,Dubai,1", 
       "Dubai,Venice,2", 
       "Venice,Rio,3", 
       "Venice,Sydney,1", 
       "Sydney,Rio,7" 
      }; 



      // lets convert the list of string into list or route 
      var routes = new List<Route>(); 
      csvLines.ForEach(s => 
      { 
       // split by , 
       string[] pieces = s.Split(','); 

       // ensure travel time is a number 
       decimal travelTime = 0; 
       decimal.TryParse(pieces[2], out travelTime); 

       // convert string to route object 
       routes.Add(new Route() 
       { 
        From = pieces[0], 
        To = pieces[1], 
        TravelTime = travelTime 
       }); 
      }); 

      // once all the data in place - the rest is easy. 
      // lets assume our FROM is sydne 
      string selectedFrom = "Sydney"; 

      // no lets find all the routes from sydney to every other place 
      // listing the shortes route first 
      // the "Where" clause allows us to filter by the selected from 
      // the order by clause allows us to order by travel time 
      var desiredRoutes = routes.Where(route => route.From == selectedFrom).OrderBy(route => route.TravelTime).ToList(); 

      // the output template allows us to format all outputs 
      // the numbers in culry bracers such as {0} {1}...etc are placeholderst that get replaced with actul values 
      // {0} = index number 
      // {1} = To 
      // {2} = duration 
      // {3} = From 
      // "To 1: Dubai, Smallest Path Length: 1, Path: Sydney, Dubai.";/ 
      string outputTemplate = "To {0}: {1}, Smallest Path Length: {2}, Path: {3}, {1}."; 


      Console.WriteLine("Selected Country: '{0}'.", selectedFrom); 

      // look through each selected route 
      for(int index = 0; index < desiredRoutes.Count; index++) 
      { 
       // ensure you access to the route variable in the current instance of the loop 
       var route = desiredRoutes[index]; 

       // write all outputs 
       // (index + 1) allows our counter to start from 1 instead of 0 
       Console.WriteLine(outputTemplate, (index + 1), route.To, route.TravelTime, route.From); 
      } 

      Console.WriteLine("Press any key to exit."); 
      Console.ReadKey(); 
     } 
    } 
} 

注：類路線：

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 
using System.Threading.Tasks; 

namespace ShortPath 
{ 
    public class Route 
    { 
     public string From { get; set; } 

     public string To { get; set; } 

     public decimal TravelTime { get; set; } 

    } 
} 

輸出應如下所示：

Selected Country: 'Sydney'. 
To 1: Dubai, Smallest Path Length: 1, Path: Sydney, Dubai. 
To 2: Rio, Smallest Path Length: 7, Path: Sydney, Rio. 
Press any key to exit. 

Answer 2

試試這個

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 
using System.Data; 


namespace ConsoleApplication1 
{ 
    class Program 
    { 
     static void Main(string[] args) 
     { 
      //this one uses strings as node names 
      Dijkstra1.Program.Dijkstra(); 
      Console.ReadLine(); 
     } 
    } 
} 
namespace Dijkstra1 
{ 
    class Program 
    { 
     //Sydney,Dubai,1 
     //Dubai,Venice,2 
     //Venice,Rio,3 
     //Venice,Sydney,1 
     //Sydney,Rio,7 
     static List<List<String>> input1 = new List<List<string>>{ 
       new List<String>() {"Sydney","0","1","7","1"}, 
       new List<String>() {"Dubai", "1","0","0","2"}, 
       new List<String>() {"Rio", "7","0","0","3"}, 
       new List<String>() {"Venice","1","2","3","0"}, 
      }; 

     static public void Dijkstra() 
     { 
      CGraph cGraph; 
      cGraph = new CGraph(input1); 
      Console.WriteLine("-------------Input 1 -------------"); 
      cGraph.PrintGraph(); 

     } 
     class CGraph 
     { 
      List<Node> graph = new List<Node>(); 
      public CGraph(List<List<String>> input) 
      { 
       foreach (List<string> inputRow in input) 
       { 
        Node newNode = new Node(); 
        newNode.name = inputRow[0]; 
        newNode.distanceDict = new Dictionary<string, Path>(); 
        newNode.visited = false; 
        newNode.neighbors = new List<Neighbor>(); 
        //for (int index = 1; index < inputRow.Count; index++) 
        //{ 
        // //skip diagnol values so you don't count a nodes distance to itself. 
        // //node count start at zero 
        // // index you have to skip the node name 
        // //so you have to subtract one from the index 
        // if ((index - 1) != nodeCount) 
        // { 
        //  string nodeName = input[index - 1][0]; 
        //  int distance = int.Parse(inputRow[index]); 
        //  newNode.distanceDict.Add(nodeName, new List<string>() { nodeName }); 
        // } 
        //} 
        graph.Add(newNode); 
       } 
       //initialize neighbors using predefined dictionary 
       for (int nodeCount = 0; nodeCount < graph.Count; nodeCount++) 
       { 
        for (int neighborCount = 0; neighborCount < graph.Count; neighborCount++) 
        { 
         //add one to neighbor count to skip Node name in index one 
         if (input[nodeCount][neighborCount + 1] != "0") 
         { 
          Neighbor newNeightbor = new Neighbor(); 
          newNeightbor.node = graph[neighborCount]; 
          newNeightbor.distance = int.Parse(input[nodeCount][neighborCount + 1]); 
          graph[nodeCount].neighbors.Add(newNeightbor); 
          Path path = new Path(); 
          path.nodeNames = new List<string>() { input[neighborCount][0] }; 
          //add one to neighbor count to skip Node name in index one 
          path.totalDistance = int.Parse(input[nodeCount][neighborCount + 1]); 
          graph[nodeCount].distanceDict.Add(input[neighborCount][0], path); 
         } 
        } 
       } 

       foreach (Node node in graph) 
       { 
        foreach (Node nodex in graph) 
        { 
         node.visited = false; 
        } 
        TransverNode(node); 
       } 
      } 
      public class Neighbor 
      { 
       public Node node { get; set; } 
       public int distance { get; set; } 
      } 
      public class Path 
      { 
       public List<string> nodeNames { get; set; } 
       public int totalDistance { get; set; } 
      } 
      public class Node 
      { 
       public string name { get; set; } 
       public Dictionary<string, Path> distanceDict { get; set; } 
       public bool visited { get; set; } 
       public List<Neighbor> neighbors { get; set; } 
      } 
      static void TransverNode(Node node) 
      { 
       if (!node.visited) 
       { 
        node.visited = true; 
        foreach (Neighbor neighbor in node.neighbors) 
        { 
         TransverNode(neighbor.node); 
         string neighborName = neighbor.node.name; 
         int neighborDistance = neighbor.distance; 
         //compair neighbors dictionary with current dictionary 
         //update current dictionary as required 
         foreach (string key in neighbor.node.distanceDict.Keys) 
         { 
          if (key != node.name) 
          { 
           int neighborKeyDistance = neighbor.node.distanceDict[key].totalDistance; 
           if (node.distanceDict.ContainsKey(key)) 
           { 
            int currentDistance = node.distanceDict[key].totalDistance; 
            if (neighborKeyDistance + neighborDistance < currentDistance) 
            { 
             List<string> nodeList = new List<string>(); 
             nodeList.AddRange(neighbor.node.distanceDict[key].nodeNames); 
             nodeList.Insert(0, neighbor.node.name); 
             node.distanceDict[key].nodeNames = nodeList; 
             node.distanceDict[key].totalDistance = neighborKeyDistance + neighborDistance; 
            } 
           } 
           else 
           { 
            List<string> nodeList = new List<string>(); 
            nodeList.AddRange(neighbor.node.distanceDict[key].nodeNames); 
            nodeList.Insert(0, neighbor.node.name); 
            Path path = new Path(); 
            path.nodeNames = nodeList; 
            path.totalDistance = neighbor.distance + neighborKeyDistance; 
            node.distanceDict.Add(key, path); 
           } 
          } 
         } 
        } 
       } 
      } 
      public void PrintGraph() 
      { 
       foreach (Node node in graph) 
       { 
        Console.WriteLine("Node : {0}", node.name); 
        foreach (string key in node.distanceDict.Keys.OrderBy(x => x)) 
        { 
         Console.WriteLine(" Distance to node {0} = {1}, Path : {2}", key, node.distanceDict[key].totalDistance, string.Join(",", node.distanceDict[key].nodeNames.ToArray())); 
        } 
       } 
      } 
     } 
    } 

}