Вопрос по алгоритму Дейкстры

Есть код, который выводит минимальные пути от начального графа до всех остальных. Как можно перебирать значения узлов чтобы выводился минимальный путь от начального графа до конечного(заданного с клавиатуры)?. dejkstra.cpp

#include "dejkstra.h"
#include <iostream>
using namespace std;
void Dijkstra(int GR[V][V], int st)
{
    int distance[V], count, index, i, u, m = st + 1;
    bool visited[V];
    for (i = 0; i < V; i++)
    {
        distance[i] = INT_MAX; visited[i] = false;
    }
    distance[st] = 0;
    for (count = 0; count < V - 1; count++)
    {
        int min = INT_MAX;
        for (i = 0; i < V; i++)
            if (!visited[i] && distance[i] <= min)
            {
                min = distance[i]; index = i;
            }
        u = index;
        visited[u] = true;
        for (i = 0; i < V; i++)
            if (!visited[i] && GR[u][i] && distance[u] != INT_MAX &&
                distance[u] + GR[u][i] < distance[i]){
                distance[i] = distance[u] + GR[u][i];
            }
    }
    for (i = 0; i < V; i++) if (distance[i] != INT_MAX)
        cout << m << " > " << i + 1 << " = " << distance[i] << endl;
    else cout << m << " > " << i + 1 << " = " << "marshryt nedostypen" << endl;
}
int main(){
    setlocale(LC_ALL, "Rus");
    int start, GR[V][V]={
                {0,0,0,0,0,0,0},
                {0,0,11,0,0,20,0},
                {0,11,0,0,0,0,0},
                {1,0,11,0,8,0,0},
                {0,0,8,0,0,0,22},
                {0,20,0,0,0,0,8},
                {0,0,0,0,22,8,0}};
    cout<<"Nachal'naya vershina >> "; cin>>start;
    Dijkstra(GR, start-1);
}

dejkstra.h

#ifndef DEJKSTRA_H
#define DEJKSTRA_H
#pragma once
const int V = 7;
void Dijkstra(int GR[V][V], int st);

#endif // DEJKSTRA_H


Ответы (1 шт):

Автор решения: MBo

Там, где обновляете минимум

if ...
    distance[i] = distance[u] + GR[u][i];

добавьте

    predok[i] = u

В конце работы пройдите по предкам от заданного конечного узла

→ Ссылка