Практикум по курсу "Алгоритмизация и программирование". Часть 2. Андрианова А.А - 122 стр.

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

А.А. Андрианова, Л.Н. Исмагилов, Т.М. Мухтарова .
// поиск непомеченной вершины, которой
// соответствует минимальный кратчайший путь из
// s-ой вершины
m=MAX_INT; v=0;
for(u=0;u<g.n;u++)
if(X[u]==0 && T[u]<m)
{
v=u+1;
m=T[u];
}
// если нет путей во все непомеченные вершины,
// пути в конечную тоже не существует
if(v==0)
{
delete [] X;
return 0;
}
// если найденная вершина является конечной,
// путь найден
if(v==t)
{
delete [] X;
return 1;
}
// конечной вершины еще не достигли, помечаем
// вершину с минимальной длиной кратчайшего пути
// как пройденную, и она становится текущей
v--;
X[v]=1;
}
}
Особо требуется пояснить, как осуществить печать найденного пути из
массива H.
Так как элемент H[i] содержит вершину, предшествующую i-ой верши-
не пути, то сам путь можно получить только в обратном порядке (от вершины
t к вершине s). Начиная с конечной вершины v=t, переходим от вершины v
к вершине H[v], пока не дойдем до начальной вершины s (для распечатки
пути в прямом порядке можно применить стек).
. . .
i=t-1;
122
А.А. Андрианова, Л.Н. Исмагилов, Т.М. Мухтарова                   .
                   // поиск непомеченной вершины, которой
                   // соответствует минимальный кратчайший путь из
                   // s-ой вершины
                   m=MAX_INT; v=0;
                   for(u=0;u

Страницы