Min

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;
        }