Алгоритм Дейкстры, вывести шаги выполнения

@look123 · Регистрация: 07.10.2016

Author24 — интернет-сервис помощи студентам

Алгоритм Дейкстры.
Мне надо немного переделать так, чтобы выводило не просто конечный результат, например от 1 к 4: 1 -> 2 -> 5 -> 4, но и промежуточные прохождения (шаги выполнения поиска короткого пути), например от 1 пошло к 2, потом к 3, то есть 1 -> 2, 1 -> 3; потом от 2 пути, например 2 -> 7, 2 -> 5 и т.д.

Я понимаю что это нужно мне взять две переменные которые отвечают за эти вершины, и вывести их через "->", но не могу найти где эту строчку кода вставить.

Помогите пожалуйста, буду очень благодарен

C++

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
 
using namespace std;
 
const int n = 10;
const int inf = 1000*1000*1000;
 
int start, g[n][n]=
     {
        {0, 20, 25, 30, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 5, 0, 10, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 10, 15, 0, 0, 0},
        {0, 0, 0, 0, 25, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 15, 0, 5, 10, 20},
        {0, 0, 0, 0, 15, 0, 10, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 15, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 10},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 10},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    };
 
int main()
{
    vector <int> d(n+5,inf),p(n+5,-1);
    vector <bool> used(n+5);
    int start = 0, finish = 9,mn,u;
    d[start] = 0;
    for (int i=0;i<n;++i){
        mn = inf, u = -1;
        for (int j=0;j<n;++j)
            if (!used[j] && d[j] < mn)
                mn = d[j], u = j;
        if (u == -1)    break;
        used[u] = true;
        for (int j=0;j<n;++j)
            if (d[j] > d[u] + g[u][j] && g[u][j] > 0 )
                d[j] = d[u] + g[u][j], p[j] = u;
    }
    vector <int> v;
    if (p[finish] == -1)
        cout<<"No way\n";
    else{
        for (int u = finish ; u != -1; u = p[u])
            v.push_back(u);
        reverse(v.begin(),v.end());
        for (int i=0;i<v.size();++i){
            if (i > 0)    cout<<"->";
            cout<<v[i];
        }
    }
    cout<<"\n"<<d[finish]<<"\n";
}

	25.05.2017, 15:51

Опции темы