Dijkstra's Algorithm Issue

Question

I'm working on a program where I have to find the shortest path between 12 cities, starting in Seattle and ending in Miami. I'm using Dijkstra's Algorithm because the paths are weighted. Here is my code so far, it all works except the answer I get is not the one I need, although it is correct.

This part of the code sets everything up as well as creates the 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 is where I create the "cities" along with creating the values 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 that I need help figuring out is when I run the program, I get: Seattle > Denver > Dallas. That answer is correct for the shortest distance to Miami, but I need the shortest distance to every city, not just Miami. I just don't know what I need to change to display that properly.

Answer 1

To my understanding, the provided code implements Dijkstra's Algorithm, modified to terminate as soon as some desired destination node is selected into the set of nodes for which the shortest path from the initial node is known. Dijkstra's algorithm solves the so-called Single Source Shortest Path problem. This means that some initial node, in this case Miami, is specified, and the desired result is consituted by the shortest paths to all other nodes. It does not solve the All-Pairs Shortest Path problem, which requires calculation of the respective distance for each pair nodes. This problem can be solved by the Floyd-Warshall Algorithm, however.

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

Answer 2

The line

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

is where you both specify the endpoint of "Miami" and write the output to the console.

You need to create a loop around that line that specifies every endpoint you want

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

This will be slow and there are things you can do such as memoization to speed it up, but should at least produce the output you want.