Уважаемые!

Спасибо большое за ответы в предыдущем посте, но к сожалению, решение так и не найдено..а очень надо..
Поэтому выкладываю еще раз с некоторыми дополнительными комментариями, которые может быть могут помочь:

Прошу помочь в такой проблеме:
Имеется ориентированный граф, в котором возможны циклы. В нем необходимо найти длиннейший (критический) путь из начальной вершины в конечную. Все дуги однонаправленны. Путь 100% существует (особенность графа).
Граф представлен в виде матрицы 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). Поэтому стандартный алгоритм нахождения критического пути не работает(также как и топологическая сортировка). Необходимо сделать так чтобы он искал длиннейший путь, при это не заходя в уже посещенные вершины. Вот как выглядит данный граф (дуги взвешенные и имеют разные значения!!):



Хочу немного уточнить про особенность графа:


Начальный граф всегда имеет такой вид:


Т.е. есть начальная вершина и есть m множеств путей(в данном примере 3, это пути 1-2-3-4-11, 1-5-6-7-11 и 1-8-9-10-11), которые состоят каждая из m вершин. В этом графе легко найти длиннейший путь — это длина длиннейшего пути (какогото из m).
Но в процессе работы начальный граф видоизменяется и, соответственно, принимает, к примеру, такой вид(все дуги взвешенные):



Изменения происходят следующие(причем в процессе работы разными способами делаются изменения в начальном графе и для каждого необходимо считать длиннейший путь из 1 в 11):
В каждом пути выбирается по одной вершине и между ними проводятся дуги, так что они образуют пути из m-1 дуг между собой(в данном примере это соответственно 9-2-7, 8-3-5, 4-10-6). После этих преобразований соответственно граф принимает вышеприведенный вид, что все-таки отличает его от произвольного ографа. Может это как-то может облегчить задачу нахождения длиннейшего пути из 1 в 11 вершину. Контуры возникают не всегда, но тем не менее могут возникать...

Спасибо за все предыдущие ответы! Но пока решения к сожалению не вижу

Вот код на C++, но он работает только для бесконтурных графов и использует топологическую сортировку(не работает с циклами) и алгоритм Флойда, адаптированный под нахождение длиннейшего пути..но повторюсь..код не работает с циклами...:

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]) 
}

P.S. Мне очень нужен этот алгоритм! Помогите плиз!!!