Вопрос по алгоритму Дейкстры
Есть код, который выводит минимальные пути от начального графа до всех остальных. Как можно перебирать значения узлов чтобы выводился минимальный путь от начального графа до конечного(заданного с клавиатуры)?. 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
В конце работы пройдите по предкам от заданного конечного узла