Floyd-Warshall Algorithm - not working on specific occasions

Question

I am trying to create a simple program using the Floyd-Warshall Algorithm to calculate the shortest route between two or more pairs of nodes.

I am using a class Village to represent the nodes, and a class Road to represent the roads between said nodes. Further down through the code I am also calling a class TransportRequest which represent the two nodes from which I need to generate the shortest path.

public string CalculateShortestRoute(List<Village> villagesList, List<Road> roadsList, Guid mapID)
    {
        //Initialize two dimentional arrays with the amount of villages.
        int[,] dist = new int[villagesList.Count, villagesList.Count];
        string[,] path = new string[villagesList.Count, villagesList.Count];

        //Loop through each village in order to insert distance values into a two dimentional array
        for (int from = 0; from < villagesList.Count; from++)
        {
            for (int to = 0; to < villagesList.Count; to++)
            {
                //If the village from and village to are the same, set the distance to 0.
                if (from == to)
                {
                    dist[from, to] = 0;
                }
                else
                {
                    int result = 1000000;

                    //Get the road between the two currently selected villages.
                    Road rDist = roadsList.SingleOrDefault<Road>(v => v.Village.Name == villagesList[from].Name && v.Village1.Name == villagesList[to].Name);

                    //If the road doesn't exist...
                    if (rDist == null)
                    {
                        //... swap the village from and village to, and check again
                        rDist = roadsList.SingleOrDefault<Road>(v => v.Village.Name == villagesList[to].Name && v.Village1.Name == villagesList[from].Name);
                        if (rDist != null)
                        {
                            //If the road is now found, get the distance.
                            result = Convert.ToInt32(rDist.Distance);
                        }
                    }
                    else
                    {
                        //If the road initially existed, get its distance.
                        result = Convert.ToInt32(rDist.Distance);
                    }

                    //Set the distance at the given positions to the integer retrieved.
                    dist[from, to] = result;
                }
            }
        }


        //Loop through all the villages again and initialize the other two dimentional array with the village name.
        for (int from = 0; from < villagesList.Count; from++)
        {
            for (int to = 0; to < villagesList.Count; to++)
            {
                path[from, to] = villagesList[from].Name;
            }
        }

        //Re-loop through all the villages three times...
        for (int k = 0; k < villagesList.Count; k++)
        {
            for (int i = 0; i < villagesList.Count; i++)
            {
                for (int j = 0; j < villagesList.Count; j++)
                {
                    if (dist[i, j] != 1000000)
                    {
                        //... and if the distances between two selected villages is greater than the other two added together, ...
                        if (dist[i, j] > (dist[i, k] + dist[k, j]))
                        {
                            //... Set the distances of the two selected villages to the shortest distance.
                            dist[i, j] = dist[i, k] + dist[k, j];
                            int distance = dist[i, j];


                            Village vv = villagesList.SingleOrDefault(v => v.Name == villagesList[k].Name);
                            //Also, add the village name to the path.
                            path[i, j] = path[i, j] + " " + vv.Name;

                        }
                    }
                }
            }
        }

        for (int from = 0; from < villagesList.Count; from++)
        {
            for (int to = 0; to < villagesList.Count; to++)
            {
                Village vv = villagesList.SingleOrDefault(v => v.Name == villagesList[to].Name);

                path[from, to] = path[from, to] + " " + vv.Name;
            }
        }

        //Get the transport requests on the current map.
        Map m = new BAMap().GetMapByID(mapID);
        List<TransportRequest> transportRequests = new BATransportRequest().GetTransportRequestsByMapID(m.ID).ToList();


        string p = "";

        int dis = 0;
        //For each transport request, get the index village from and village to from the map vilalges.
        foreach (TransportRequest r in transportRequests)
        {

            int villFrom = villagesList.IndexOf(villagesList.Single<Village>(vill => vill.Name == r.Village.Name));
            int villTo = villagesList.IndexOf(villagesList.Single<Village>(vill => vill.Name == r.Village1.Name));

            //Retrieve the distance between these two villages from the two dimentional array
            dis = dist[villFrom, villTo];

            //Initialize a string 'p' to null.
            //If it is null...
            if (p == "")
            {
                //... add the path of the village from and village to.
                p = path[villFrom, villTo];
            }
            else
            {
                //Else, if it is not null, add the path of the village from and village to to the string.
                p += " " + path[villFrom, villTo];
            }
        }

        //If the string doesn't start with an 'A'...
        if (!p.StartsWith("A"))
        {
            string pp = p;
            //.. Start the path from village 'A', and add the path retreived beforehand to the 'A'
            p = "A " + pp;
        }

        //If the final path doesn't end with an 'A'...
        if (!p.EndsWith("A"))
        {
            //... attach an 'A' to it.
            p += " A";
        }

        //Return the path.
        return p;

    }

The above code seems to work fine on most of the randomly generated nodes and distances, however fails on a few occasions such as the one below;

If I try to calculate the shortest route from node A to node E, the answer is always A > E (with a total of 100) instead of A > B > C > D > E (with a total of 37).

The roads between each node are bi-directional, meaning that from A to B and B to A are both 10, in this case.

The matrices dist[] is being populated correctly with the correct distances between each node pair. Where there is no road connecting the pair of nodes, I am setting a default distance of 1000000 units.

I've searched through multiple questions on different forums (including this one) but none seem to tackle this issue. I believe that the algorithm is implemented correctly but I fail to see where and why on certain occasions it doesn't work properly.

I would greatly appreciate help on this matter as I've been working trying to solve this issue for more than a week.

Many thanks in advance.

Answer 1

This is because you never allow to reduce the dist between two nodes not connected by a road. Look for example at node C and E. The dist[C,E] will remain 1000000 because you never consider the possibility of going from C to E via D.

By the way, a quick debug session would have probably been the way to go to see what the algorithm is doing step by step.