Dijkstra's Algorithm Problem

Question

I am working on a program where I need to find the shortest path between 12 cities, starting from Seattle and ending in Miami. I use the Dijkstra Algorithm because the paths are weighted. Here is my code so far, everything works, except that I am not getting the one I need, although it is correct.

This piece of code sets everything up and also creates a sorting algorithm.

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; } } 

Below I create "cities" along with creating meanings between them.

 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 + " > ")); } } 

The part I need will help find out when I run the program, I get: Seattle> Denver> Dallas. This answer is correct for the shortest distance to Miami, but I need the shortest distance to each city, not just Miami. I just don’t know what I need to change in order to display correctly.

Answer 1

As far as I understand, the provided code implements the Dijkstra Algorithm , modified for completion, as soon as the node of the node for which the shortest path from the initial node is known is selected at the desired destination. Dijkstra's algorithm solves the Single Source Shortest Path problem. This means that an initial node is specified, in this case Miami , and the desired result is borrowed by the shortest paths to all other nodes. It does not solve the All-Pairs Shortest Path problem, which requires the calculation of the corresponding distance for each pair of nodes. However, this problem can be solved by the Floyd-Warshall Algorithm .

In contrast, if you need the shortest path from Miami to all other cities, change the implementation of not to break the loop earlier and remove the second argument.

Answer 2

Line

  g.shortest_path("Miami", "Seattle").ForEach(x => Console.Write(x + " > ")); 

where you both indicate the endpoint "Miami" and write the output to the console.

You need to create a loop around this line that indicates each endpoint that you want

 foreach(var endpoint in validEndpoints) { g.shortest_path(endpoint, "Seattle").ForEach(x => Console.Write(x + " > ")); } 

This will be slow, and you can do things like memoization to speed it up, but you should at least produce the desired result.

Answer 3

I have been sending this code for many years. You need a recursive algorithm.

 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(); //this one uses integers as node names Dijkstra2.Program.Dijkstra(); } } } namespace Dijkstra1 { class Program { //A connected to B //B connected to A, C , D //C connected to B, D //D connected to B, C , E //E connected to D. static List<List<String>> input1 = new List<List<string>>{ new List<String>() {"A","0","1","0","0","0"}, new List<String>() {"B","1","0","1","1","0"}, new List<String>() {"C","0","1","0","1","0"}, new List<String>() {"D","0","1","1","0","1"}, new List<String>() {"E","0","0","0","1","0"} }; //A | 0 1 2 2 3 | //B | 1 0 1 1 2 | //C | 2 1 0 1 2 | //D | 2 1 1 0 1 | //E | 3 2 2 1 0 | static List<List<String>> input2 = new List<List<string>>{ new List<String>() {"A","0","1","2","2","3"}, new List<String>() {"B","1","0","1","1","2"}, new List<String>() {"C","2","1","0","1","2"}, new List<String>() {"D","2","1","1","0","1"}, new List<String>() {"E","3","2","2","1","0"} }; static public void Dijkstra() { CGraph cGraph; cGraph = new CGraph(input1); Console.WriteLine("-------------Input 1 -------------"); cGraph.PrintGraph(); cGraph = new CGraph(input2); Console.WriteLine("-------------Input 2 -------------"); 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 Boolean 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())); } } } } } } namespace Dijkstra2 { class Program { //0---1---2---3 // | // 4 // | // 5---6---7 // \ / // 8 // | // 9 static List<List<int>> input1 = new List<List<int>> { // 0 1 2 3 4 5 6 7 8 9 new List<int>() {0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0}, new List<int>() {1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0}, new List<int>() {2, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0}, new List<int>() {3, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0}, new List<int>() {4, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0}, new List<int>() {5, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0}, new List<int>() {6, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0}, new List<int>() {7, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0}, new List<int>() {8, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1}, new List<int>() {9, 0, 0, 0, 0, 0, 0, 0, 0, 1, 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<int>> input) { foreach (List<int> inputRow in input) { Node newNode = new Node(); newNode.name = inputRow[0]; newNode.distanceDict = new Dictionary<int, 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 = input[nodeCount][neighborCount + 1]; graph[nodeCount].neighbors.Add(newNeightbor); Path path = new Path(); path.nodeNames = new List<int>() { input[neighborCount][0] }; //add one to neighbor count to skip Node name in index one path.totalDistance = 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<int> nodeNames { get; set; } public int totalDistance { get; set; } } public class Node { public int name { get; set; } public Dictionary<int, Path> distanceDict { get; set; } public Boolean 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); int neighborName = neighbor.node.name; int neighborDistance = neighbor.distance; //compair neighbors dictionary with current dictionary //update current dictionary as required foreach (int 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<int> nodeList = new List<int>(); 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<int> nodeList = new List<int>(); 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 (int 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())); } } } } } }​