Алгоритм Дейкстра. Поиск кратчайшего пути с запоминанием маршрута

void Graph::Dijkstra() {
    int index;
 
    int *distance = new int[size];
    int *visited = new int[size];
 
    int ** info = new int *[size];
    for (int i = 0; i < size; i++) {
        info[i] = new int[size];
    }
 
 
    for (int i = 0; i < size; i++) {
        distance[i] = INT_MAX;
        visited[i] = 0;
    }
 
    distance[Capital-1] = 0;
 
    for (int count = 0; count < size - 1; count++){
        int min = INT_MAX;
 
        for (int i = 0; i < size; i++) {
            if (!visited[i] && distance[i] <= min) {
                min = distance[i]; index = i;
            }
        }
 
        visited[index] = 1;
        for (int i = 0; i < size; i++) {
            if (!visited[i] && Matrix[index][i] && distance[index] != INT_MAX && distance[index] + Matrix[index][i] < distance[i]) {
                distance[i] = distance[index] + Matrix[index][i];
            }
        }
    }
}

9
1 20 40 0 55 81 0 25 15
20 1 10 0 0 0 0 0 35
40 10 1 5 0 0 15 0 0
0 0 5 1 55 0 0 80 0
55 0 0 55 1 5 0 0 0
81 0 0 0 5 1 25 8 0
0 0 15 0 0 25 1 5 0
25 0 0 80 0 8 5 1 12
15 35 0 0 0 0 0 12 1

void Graph::Floyd() {
    for (int k = 0; k < size; ++k)
        for (int i = 0; i < size; ++i)
            for (int j = 0; j < size; ++j) {
                if (Matrix[i][k] + Matrix[k][j] < Matrix[i][j]) {
                    Matrix[i][j] = Matrix[i][k] + Matrix[k][j];
                    Predok[i][j] = k;
                }
            }
}