Floyd-Warshall Algorithm - not working on specific occasions
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.
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.