Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- for (u = 0; u < p; u++)
- {
- t[u] = infinity; //Сначала все кратчайшие пути из s в i
- //равны бесконечности
- x[u] = 0; // и нет кратчайшего пути ни для одной вершины
- }
- h[s] = 0; // s - начало пути, поэтому этой вершине ничего не предшествует
- t[s] = 0; // Кратчайший путь из s в s равен 0
- x[s] = 1; // Для вершины s найден кратчайший путь
- v = s; // Делаем s текущей вершиной
- while (1)
- {
- // Перебираем все вершины, смежные v, и ищем для них кратчайший путь
- for (u = 0; u < p; u++)
- {
- if (a[v][u] == 0) continue; // Вершины u и v несмежные
- if (x[u] == 0 && t[u] > t[v] + a[v][u]) //Если для вершины u еще не
- //найден кратчайший путь
- // и новый путь в u короче чем
- //старый, то
- {
- t[u] = t[v] + a[v][u]; //запоминаем более короткую длину пути в
- //массив t и
- h[u] = v; //запоминаем, что v->u часть кратчайшего
- //пути из s->u
- }
- }
- // Ищем из всех длин некратчайших путей самый короткий
- int w = infinity; // Для поиска самого короткого пути
- v = -1; // В конце поиска v - вершина, в которую будет
- // найден новый кратчайший путь. Она станет
- // текущей вершиной
- for (u = 0; u < p; u++) // Перебираем все вершины.
- {
- if (x[u] == 0 && t[u] < w) // Если для вершины не найден кратчайший
- // путь и если длина пути в вершину u меньше
- // уже найденной, то
- {
- v = u; // текущей вершиной становится u-я вершина
- w = t[u];
- }
- }
- if (v == -1)
- {
- cout << "Нет пути из вершины " << s << " в вершину " << g << "." << endl;
- break;
- }
- if (v == g) // Найден кратчайший путь,
- { // выводим его
- cout << "Кратчайший путь из вершины " << s << " в вершину " << g << ":";
- u = g;
- while (u != s)
- {
- cout << " " << u;
- u = h[u];
- }
- cout << " " << s << ". Длина пути - " << t[g];
- break;
- }
- x[v] = 1;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement