Следующая проблема:
Нужен алгоритм нахождения критического (длиннейшего) пути в орграфе от самой первой вершины до последней (от 0 до m-1), представленного в виде матрицы m x m типа:
| Код |
{
{-Inf, 0,-Inf, -Inf, 0, -Inf, -Inf, 0, -Inf, -Inf, -Inf},
{-Inf, -Inf,10, -Inf, -Inf, -Inf, -Inf, -Inf,10, -Inf, -Inf},
{-Inf, -Inf,-Inf, 8,8, -Inf, -Inf, -Inf, -Inf, -Inf, -Inf},
{-Inf, -Inf,-Inf, -Inf, -Inf, -Inf, -Inf, -Inf, -Inf, 4, 4},
{-Inf, -Inf,-Inf, -Inf, -Inf, 5, -Inf, -Inf, -Inf, -Inf, -Inf},
{-Inf, -Inf,-Inf, -Inf, -Inf, -Inf, 5, -Inf, -Inf, -Inf, -Inf},
{-Inf,6,-Inf, -Inf, -Inf, -Inf, -Inf, -Inf, -Inf, -Inf, 6},
{-Inf, -Inf,4, -Inf, -Inf, -Inf, -Inf, -Inf, 4, -Inf, -Inf},
{-Inf, -Inf,-Inf, -Inf, -Inf, -Inf, -Inf, -Inf, -Inf, 7, -Inf},
{-Inf, -Inf,-Inf, -Inf, -Inf,3, -Inf, -Inf, -Inf, -Inf, 3},
{-Inf, -Inf,-Inf, -Inf, -Inf, -Inf, -Inf, -Inf, -Inf, -Inf, -Inf}}
|
Вышеприведенный пример представляет собой ориентированный граф, внутри которого есть циклы (цикл путь: 2-3-5-6-7-2). Поэтому стандартный алгоритм нахождения критического пути не работает. Необходимо сделать так чтобы он искал длиннейший путь, при это не заходя в уже посещенные вершины. На данный момент есть следующий код, но он не похоже не работает при зацикливании:
| Код |
void Topological_Sort () //Процедура топологической сортировки
{
int Children[n];
int index=n-1;
{for (int v=0; v<n; v++) Children[v]=0;}
{for (int v=0; v<n; v++)
for (int v2=0; v2<n; v2++)
if (graph[v][v2]!=Inf && v2!=v) Children[v]++;}
bool found;
do {
found=false;
for (int v=0; v<n; v++)
if (!Children[v]) {
for (int p=0; p<n; p++) if (graph[p][v]!=Inf) Children[p]--;
Children[v]=1;
Order[index--]=v;
found=true;
break;
}
} while (found);
}
int dist(int s, int d) //Процедура для подсчета длины длиннейшего пути в графе
//Мы принимаем, что есть только одна начальная и одна конечная вершина, и нам необходимо найти длиннейший путь
{
//1 - Делаем топологическую сортировку множества вершин: V->Order[]
Topological_Sort();
//Первая будет все время в Order[0], тогда как последняя в Order[n-1]
//2 - Используем техничку динамического программирования
// Rule: Dist[d]=max{Dist[v]+graph[v][d], (v,d) in E}
int Dist[n];
int v;
{for (int v=0; v<n; v++) Dist[v]=graph[s][v];}
Dist[s]=0;
for (int i=0; i<n; i++) {
v=Order[i];
for (int pred=0; pred<n; pred++) if (graph[pred][v]!=Inf)
if (Dist[pred]+graph[pred][v]>Dist[v]) Dist[v]=Dist[pred]+graph[pred][v];
}
return Dist[d]; //Возвращаем последнею величину v (=Order[n-1])
}
|
Возможно, как-то можно внести изменение в этот код, чтобы решалось нормально. Помогите плиз!!!! |