Я пытаюсь создать простую программу с использованием алгоритма Флойда-Уоршалла для расчета кратчайшего маршрута между двумя или более парами узлов.
Я использую класс 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 единиц.
Я просмотрел несколько вопросов на разных форумах (включая этот), но, похоже, никто не решает эту проблему. Я считаю, что алгоритм реализован правильно, но я не вижу, где и почему в определенных случаях он не работает должным образом.
Я был бы очень признателен за помощь в этом вопросе, так как я работаю над решением этой проблемы уже более недели.
Спасибо заранее.
