我正在尝试使用 Floyd-Warshall 算法创建一个简单的程序来计算两对或多对节点之间的最短路径。
我正在使用一个类Village来表示节点，并使用一个类来表示Road所述节点之间的道路。通过代码，我还调用了一个类TransportRequest，该类代表我需要从中生成最短路径的两个节点。
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;
}
上面的代码似乎在大多数随机生成的节点和距离上都可以正常工作，但是在少数情况下会失败，例如下面的代码；
如果我尝试计算从节点 A 到节点 E 的最短路径，答案总是 A > E（总共 100）而不是 A > B > C > D > E（总共 37）。
每个节点之间的道路是双向的，这意味着从 A 到 B 和 B 到 A 都是 10，在这种情况下。
使用每个节点对之间的正确距离正确填充了矩阵 dist[]。如果没有连接这对节点的道路，我将默认距离设置为 1000000 个单位。
我在不同的论坛（包括这个）上搜索了多个问题，但似乎没有一个可以解决这个问题。我相信该算法已正确实施，但我看不出在某些情况下它在哪里以及为什么不能正常工作。
我非常感谢在这个问题上的帮助，因为我已经努力解决这个问题一个多星期了。
提前谢谢了。