Azu*_*cho 5 c# dijkstra console-application
我正在开展一个项目,我必须找到12个城市之间的最短路径,从西雅图开始,到迈阿密结束.我正在使用Dijkstra的算法,因为路径是加权的.到目前为止,这是我的代码,除了我得到的答案不是我需要的答案之外,它都有效,尽管它是正确的.
这部分代码设置了所有内容以及创建排序算法.
class Graph
{
Dictionary<string, Dictionary<string, int>> vertices = new Dictionary<string, Dictionary<string, int>>();
public void add_vertex(string name, Dictionary<string, int> edges)
{
vertices[name] = edges;
}
public List<string> shortest_path(string start, string finish)
{
var previous = new Dictionary<string, string>();
var distances = new Dictionary<string, int>();
var nodes = new List<string>();
List<string> path = null;
foreach (var vertex in vertices)
{
if (vertex.Key == start)
{
distances[vertex.Key] = 1;
}
else
{
distances[vertex.Key] = int.MaxValue;
}
nodes.Add(vertex.Key);
}
while (nodes.Count != 0)
{
nodes.Sort((x, y) => distances[x] - distances[y]);
var smallest = nodes[0];
nodes.Remove(smallest);
if (smallest == finish)
{
path = new List<string>();
while (previous.ContainsKey(smallest))
{
path.Add(smallest);
smallest = previous[smallest];
}
break;
}
if (distances[smallest] == int.MaxValue)
{
break;
}
foreach (var neighbor in vertices[smallest])
{
var alt = distances[smallest] + neighbor.Value;
if (alt < distances[neighbor.Key])
{
distances[neighbor.Key] = alt;
previous[neighbor.Key] = smallest;
}
}
}
return path;
}
}
下面是我创建"城市"以及在它们之间创建值的地方.
class MainClass
{
public static void Main(string[] args)
{
Graph g = new Graph();
g.add_vertex("Seattle", new Dictionary<string, int>() { {"San Francisco", 1306}, {"Denver", 2161}, {"Minneapolis", 2661} });
g.add_vertex("San Francisco", new Dictionary<string, int>() { {"Seattle", 1306}, {"Las Vegas", 919}, {"Los Angeles", 629} });
g.add_vertex("Las Vegas", new Dictionary<string, int>() { {"San Francisco", 919}, {"Los Angeles", 435}, {"Denver", 1225}, {"Dallas", 1983} });
g.add_vertex("Los Angeles", new Dictionary<string, int>() { {"San Francisco", 629}, {"Las Vegas", 435} });
g.add_vertex("Denver", new Dictionary<string, int>() { {"Seattle", 2161}, {"Las Vegas", 1225}, {"Minneapolis", 1483}, {"Dallas", 1258} });
g.add_vertex("Minneapolis", new Dictionary<string, int>() { {"Seattle", 2661}, {"Denver", 1483}, {"Dallas", 1532}, {"Chicago", 661} });
g.add_vertex("Dallas", new Dictionary<string, int>() { {"Las Vegas", 1983}, {"Denver", 1258}, {"Minneapolis", 1532}, {"Washington DC", 2113} });
g.add_vertex("Chicago", new Dictionary<string, int>() { {"Minneapolis", 661}, {"Washington DC", 1145}, {"Boston", 1613} });
g.add_vertex("Washington DC", new Dictionary<string, int>() { {"Dallas", 2113}, {"Chicago", 1145}, {"Boston", 725}, {"New York", 383}, {"Miami", 1709} });
g.add_vertex("Boston", new Dictionary<string, int>() { {"Chicago", 1613}, {"Washington DC", 725}, {"New York", 338} });
g.add_vertex("New York", new Dictionary<string, int>() { {"Washington DC", 383}, {"Boston", 338}, {"Miami", 2145} });
g.add_vertex("Miami", new Dictionary<string, int>() { {"Dallas", 2161}, {"Washington DC", 1709}, {"New York", 2145} });
g.shortest_path("Miami", "Seattle").ForEach(x => Console.Write(x + " > "));
}
}
我需要帮助解决的部分是当我运行程序时,我得到:西雅图>丹佛>达拉斯.这个答案对迈阿密的最短距离是正确的,但我需要到每个城市的最短距离,而不仅仅是迈阿密.我只是不知道我需要改变什么才能正确显示.
我多年来一直发布此代码。你需要一个递归算法。
\n\nusing System;\r\nusing System.Collections.Generic;\r\nusing System.Linq;\r\nusing System.Text;\r\nusing System.Data;\r\n\r\n\r\nnamespace ConsoleApplication1\r\n{\r\n class Program\r\n {\r\n static void Main(string[] args)\r\n {\r\n //this one uses strings as node names\r\n Dijkstra1.Program.Dijkstra();\r\n //this one uses integers as node names\r\n Dijkstra2.Program.Dijkstra();\r\n }\r\n }\r\n}\r\nnamespace Dijkstra1\r\n{\r\n class Program\r\n {\r\n //A connected to B\r\n //B connected to A, C , D\r\n //C connected to B, D\r\n //D connected to B, C , E\r\n //E connected to D.\r\n static List<List<String>> input1 = new List<List<string>>{\r\n new List<String>() {"A","0","1","0","0","0"},\r\n new List<String>() {"B","1","0","1","1","0"},\r\n new List<String>() {"C","0","1","0","1","0"},\r\n new List<String>() {"D","0","1","1","0","1"},\r\n new List<String>() {"E","0","0","0","1","0"}\r\n };\r\n //A | 0 1 2 2 3 |\r\n //B | 1 0 1 1 2 |\r\n //C | 2 1 0 1 2 | \r\n //D | 2 1 1 0 1 |\r\n //E | 3 2 2 1 0 |\r\n static List<List<String>> input2 = new List<List<string>>{\r\n new List<String>() {"A","0","1","2","2","3"},\r\n new List<String>() {"B","1","0","1","1","2"},\r\n new List<String>() {"C","2","1","0","1","2"},\r\n new List<String>() {"D","2","1","1","0","1"},\r\n new List<String>() {"E","3","2","2","1","0"}\r\n };\r\n static public void Dijkstra()\r\n {\r\n CGraph cGraph;\r\n cGraph = new CGraph(input1);\r\n Console.WriteLine("-------------Input 1 -------------");\r\n cGraph.PrintGraph();\r\n cGraph = new CGraph(input2);\r\n Console.WriteLine("-------------Input 2 -------------");\r\n cGraph.PrintGraph();\r\n }\r\n class CGraph\r\n {\r\n List<Node> graph = new List<Node>();\r\n public CGraph(List<List<String>> input)\r\n {\r\n foreach (List<string> inputRow in input)\r\n {\r\n Node newNode = new Node();\r\n newNode.name = inputRow[0];\r\n newNode.distanceDict = new Dictionary<string, Path>();\r\n newNode.visited = false;\r\n newNode.neighbors = new List<Neighbor>();\r\n //for (int index = 1; index < inputRow.Count; index++)\r\n //{\r\n // //skip diagnol values so you don\'t count a nodes distance to itself.\r\n // //node count start at zero\r\n // // index you have to skip the node name\r\n // //so you have to subtract one from the index\r\n // if ((index - 1) != nodeCount)\r\n // {\r\n // string nodeName = input[index - 1][0];\r\n // int distance = int.Parse(inputRow[index]);\r\n // newNode.distanceDict.Add(nodeName, new List<string>() { nodeName });\r\n // } \r\n //}\r\n graph.Add(newNode);\r\n }\r\n //initialize neighbors using predefined dictionary\r\n for (int nodeCount = 0; nodeCount < graph.Count; nodeCount++)\r\n {\r\n for (int neighborCount = 0; neighborCount < graph.Count; neighborCount++)\r\n {\r\n //add one to neighbor count to skip Node name in index one\r\n if (input[nodeCount][neighborCount + 1] != "0")\r\n {\r\n Neighbor newNeightbor = new Neighbor();\r\n newNeightbor.node = graph[neighborCount];\r\n newNeightbor.distance = int.Parse(input[nodeCount][neighborCount + 1]);\r\n graph[nodeCount].neighbors.Add(newNeightbor);\r\n Path path = new Path();\r\n path.nodeNames = new List<string>() { input[neighborCount][0] };\r\n //add one to neighbor count to skip Node name in index one\r\n path.totalDistance = int.Parse(input[nodeCount][neighborCount + 1]);\r\n graph[nodeCount].distanceDict.Add(input[neighborCount][0], path);\r\n }\r\n }\r\n }\r\n\r\n foreach (Node node in graph)\r\n {\r\n foreach (Node nodex in graph)\r\n {\r\n node.visited = false;\r\n }\r\n TransverNode(node);\r\n }\r\n }\r\n public class Neighbor\r\n {\r\n public Node node { get; set; }\r\n public int distance { get; set; }\r\n }\r\n public class Path\r\n {\r\n public List<string> nodeNames { get; set; }\r\n public int totalDistance { get; set; }\r\n }\r\n public class Node\r\n {\r\n public string name { get; set; }\r\n public Dictionary<string, Path> distanceDict { get; set; }\r\n public Boolean visited { get; set; }\r\n public List<Neighbor> neighbors { get; set; }\r\n }\r\n static void TransverNode(Node node)\r\n {\r\n if (!node.visited)\r\n {\r\n node.visited = true;\r\n foreach (Neighbor neighbor in node.neighbors)\r\n {\r\n TransverNode(neighbor.node);\r\n string neighborName = neighbor.node.name;\r\n int neighborDistance = neighbor.distance;\r\n //compair neighbors dictionary with current dictionary\r\n //update current dictionary as required\r\n foreach (string key in neighbor.node.distanceDict.Keys)\r\n {\r\n if (key != node.name)\r\n {\r\n int neighborKeyDistance = neighbor.node.distanceDict[key].totalDistance;\r\n if (node.distanceDict.ContainsKey(key))\r\n {\r\n int currentDistance = node.distanceDict[key].totalDistance;\r\n if (neighborKeyDistance + neighborDistance < currentDistance)\r\n {\r\n List<string> nodeList = new List<string>();\r\n nodeList.AddRange(neighbor.node.distanceDict[key].nodeNames);\r\n nodeList.Insert(0, neighbor.node.name);\r\n node.distanceDict[key].nodeNames = nodeList;\r\n node.distanceDict[key].totalDistance = neighborKeyDistance + neighborDistance;\r\n }\r\n }\r\n else\r\n {\r\n List<string> nodeList = new List<string>();\r\n nodeList.AddRange(neighbor.node.distanceDict[key].nodeNames);\r\n nodeList.Insert(0, neighbor.node.name);\r\n Path path = new Path();\r\n path.nodeNames = nodeList;\r\n path.totalDistance = neighbor.distance + neighborKeyDistance;\r\n node.distanceDict.Add(key, path);\r\n }\r\n }\r\n }\r\n }\r\n }\r\n }\r\n public void PrintGraph()\r\n {\r\n foreach (Node node in graph)\r\n {\r\n Console.WriteLine("Node : {0}", node.name);\r\n foreach (string key in node.distanceDict.Keys.OrderBy(x => x))\r\n {\r\n Console.WriteLine(" Distance to node {0} = {1}, Path : {2}", key, node.distanceDict[key].totalDistance, string.Join(",", node.distanceDict[key].nodeNames.ToArray()));\r\n }\r\n }\r\n }\r\n }\r\n }\r\n\r\n}\r\nnamespace Dijkstra2\r\n{\r\n class Program\r\n {\r\n //0---1---2---3\r\n // |\r\n // 4\r\n // |\r\n // 5---6---7\r\n // \\ /\r\n // 8\r\n // |\r\n // 9 \r\n \r\n static List<List<int>> input1 = new List<List<int>>\r\n { // 0 1 2 3 4 5 6 7 8 9\r\n new List<int>() {0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},\r\n new List<int>() {1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0},\r\n new List<int>() {2, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0},\r\n new List<int>() {3, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0},\r\n new List<int>() {4, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0},\r\n new List<int>() {5, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0},\r\n new List<int>() {6, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0},\r\n new List<int>() {7, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0},\r\n new List<int>() {8, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1},\r\n new List<int>() {9, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0},\r\n }; \r\n \r\n static public void Dijkstra()\r\n {\r\n CGraph cGraph;\r\n cGraph = new CGraph(input1);\r\n Console.WriteLine("-------------Input 1 -------------");\r\n cGraph.PrintGraph();\r\n }\r\n class CGraph\r\n {\r\n List<Node> graph = new List<Node>();\r\n public CGraph(List<List<int>> input)\r\n {\r\n foreach (List<int> inputRow in input)\r\n {\r\n Node newNode = new Node();\r\n newNode.name = inputRow[0];\r\n newNode.distanceDict = new Dictionary<int, Path>();\r\n newNode.visited = false;\r\n newNode.neighbors = new List<Neighbor>();\r\n //for (int index = 1; index < inputRow.Count; index++)\r\n //{\r\n // //skip diagnol values so you don\'t count a nodes distance to itself.\r\n // //node count start at zero\r\n // // index you have to skip the node name\r\n // //so you have to subtract one from the index\r\n // if ((index - 1) != nodeCount)\r\n // {\r\n // string nodeName = input[index - 1][0];\r\n // int distance = int.Parse(inputRow[index]);\r\n // newNode.distanceDict.Add(nodeName, new List<string>() { nodeName });\r\n // } \r\n //}\r\n graph.Add(newNode);\r\n }\r\n //initialize neighbors using predefined dictionary\r\n for (int nodeCount = 0; nodeCount < graph.Count; nodeCount++)\r\n {\r\n for (int neighborCount = 0; neighborCount < graph.Count; neighborCount++)\r\n {\r\n //add one to neighbor count to skip Node name in index one\r\n if (input[nodeCount][neighborCount + 1] != 0)\r\n {\r\n Neighbor newNeightbor = new Neighbor();\r\n newNeightbor.node = graph[neighborCount];\r\n newNeightbor.distance = input[nodeCount][neighborCount + 1];\r\n graph[nodeCount].neighbors.Add(newNeightbor);\r\n Path path = new Path();\r\n path.nodeNames = new List<int>() { input[neighborCount][0] };\r\n //add one to neighbor count to skip Node name in index one\r\n path.totalDistance = input[nodeCount][neighborCount + 1];\r\n graph[nodeCount].distanceDict.Add(input[neighborCount][0], path);\r\n }\r\n }\r\n }\r\n\r\n foreach (Node node in graph)\r\n {\r\n foreach (Node nodex in graph)\r\n {\r\n node.visited = false;\r\n }\r\n TransverNode(node);\r\n }\r\n }\r\n public class Neighbor\r\n {\r\n public Node node { get; set; }\r\n public int distance { get; set; }\r\n }\r\n public class Path\r\n {\r\n public List<int> nodeNames { get; set; }\r\n public int totalDistance { get; set; }\r\n }\r\n public class Node\r\n {\r\n public int name { get; set; }\r\n public Dictionary<int, Path> distanceDict { get; set; }\r\n public Boolean visited { get; set; }\r\n public List<Neighbor> neighbors { get; set; }\r\n }\r\n static void TransverNode(Node node)\r\n {\r\n if (!node.visited)\r\n {\r\n node.visited = true;\r\n foreach (Neighbor neighbor in node.neighbors)\r\n {\r\n TransverNode(neighbor.node);\r\n int neighborName = neighbor.node.name;\r\n int neighborDistance = neighbor.distance;\r\n //compair neighbors dictionary with current dictionary\r\n //update current dictionary as required\r\n foreach (int key in neighbor.node.distanceDict.Keys)\r\n {\r\n if (key != node.name)\r\n {\r\n int neighborKeyDistance = neighbor.node.distanceDict[key].totalDistance;\r\n if (node.distanceDict.ContainsKey(key))\r\n {\r\n int currentDistance = node.distanceDict[key].totalDistance;\r\n if (neighborKeyDistance + neighborDistance < currentDistance)\r\n {\r\n List<int> nodeList = new List<int>();\r\n nodeList.AddRange(neighbor.node.distanceDict[key].nodeNames);\r\n nodeList.Insert(0, neighbor.node.name);\r\n node.distanceDict[key].nodeNames = nodeList;\r\n node.distanceDict[key].totalDistance = neighborKeyDistance + neighborDistance;\r\n }\r\n }\r\n else\r\n {\r\n List<int> nodeList = new List<int>();\r\n nodeList.AddRange(neighbor.node.distanceDict[key].nodeNames);\r\n nodeList.Insert(0, neighbor.node.name);\r\n Path path = new Path();\r\n path.nodeNames = nodeList;\r\n path.totalDistance = neighbor.distance + neighborKeyDistance;\r\n node.distanceDict.Add(key, path);\r\n }\r\n }\r\n }\r\n }\r\n }\r\n }\r\n public void PrintGraph()\r\n {\r\n foreach (Node node in graph)\r\n {\r\n Console.WriteLine("Node : {0}", node.name);\r\n foreach (int key in node.distanceDict.Keys.OrderBy(x => x))\r\n {\r\n Console.WriteLine(" Distance to node {0} = {1}, Path : {2}", key, node.distanceDict[key].totalDistance, string.Join(",", node.distanceDict[key].nodeNames.ToArray()));\r\n }\r\n }\r\n }\r\n }\r\n }\r\n\r\n}\r\n\r\n\xe2\x80\x8b