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

@Aecttann · Регистрация: 19.10.2013

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

Реализация алгоритма Дейкстра.
В массиве distance - найденные кратчайшие пути, visited - логический, для хранения информации о посещенных вершинах.
Вместо "нубского" вывода пройденного пути из первой вершины в последнюю, необходимо реализовать нормальный вывод точек, через которые был проложен путь.

C++
1
cout << "А(" << distance [u-8] << ")" << " -> " << " Б(" << distance [u-7] << ")" << " -> " << " E(" << distance[5] << ")" << " -> " << " Ж(" << distance[6] << ")" << " -> " << " З(" << distance[u-1] << ")" << " -> " << " K(" << distance[u] << ")" << endl;

Кликните здесь для просмотра всего текста

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <iostream>
#include <windows.h>
#include <stdio.h>
#include <stdlib.h>
 
using namespace std;
 
const int V=10;
 
void Dejkstra(int GR[V][V], int st)
{
    int max=100;
    int distance[V], count, index, i, u, m=st+1;
    bool visited[V];
 
    for (i=0; i<V; i++)
    {
        distance[i]=max;
        visited[i]=false;
    }
 
    distance[st]=0;
 
    for (count=0; count<V-1; count++)
 
        {
            int min=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]!=max &&
            distance[u]+GR[u][i]<distance[i])
            distance[i]=distance[u]+GR[u][i];
        }
        cout<<"Длина пути Винни до пятака:\n";
 
        //for (i=0; i<V; i++)
            if (distance[i]!=max)
           // cout<<m<<" > "<<i+1<<" = "<<distance[i]<< " Пройденные точки: "   << endl;
 
            cout<<m<<" > "<<V<<" = "<<distance[u] << endl << endl;
 
       // else  cout<<m<<" > "<<i+1<<" = "<<"маршрут недоступен"<<endl << endl;
 
 
       // if (m==1)
 
            cout << endl;
            cout << "Путь из точки А к точке К: " << endl;
            cout << "А(" << distance [u-8] << ")" << " -> " << " Б(" << distance [u-7] << ")" << " -> " << " E(" << distance[5] << ")" << " -> " << " Ж(" << distance[6] << ")" << " -> " << " З(" << distance[u-1] << ")" << " -> " << " K(" << distance[u] << ")" << endl;
 
 
            cout << endl << "Медведю пилить до хрю-хрю аж " << distance[i-1]  << " чего-то там!";
 
        if (distance[i-1] > 40 )
        {   Sleep (4000);
            cout << endl << endl << "Может, домой вернуться? :(" << endl << endl; Sleep (2000);
            cout << "Кажется, дождь начинается... :(" << endl;Sleep(1500);}
}
 
 
int main()
 
{
    setlocale(LC_ALL, "Rus");
 
    int start, GR[V][V]=
    {
        {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, 0, 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},
    };
 
 
        cout<<"Начальная вершина >> ";
 
        start = 1;
 
       /* if ((start > 10)||(start < 1))
        {
            cout<<"Шот не то..." << endl;
            Sleep (3000);
            cout << "Думаю..." << endl;
            Sleep (3000);
 
            cout << "Ищем ошибку..." << endl << endl;
            Sleep (3000);
            cout << "Неверный ввод!" << endl;
            Sleep(3000);
            cout << "Аварийное завершение работы..." << endl;
            Sleep (3000);
            system("cls");
            cout<<"Давай, до свидания!";
 
            return 0;
        }
*/
        Dejkstra(GR, start-1);
}

@iliya785 · 04.06.2014, 02:36

http://e-maxx.ru/algo/dijkstra , прочитай пункт восстановление пути

@Aecttann · 04.06.2014, 03:03 **[ТС]**

iliya785, читал, читаю - ничего не выходит

@iliya785 · 04.06.2014, 22:22

если всё так плохо , то могу допилить , а также подебажить код. Также могу объяснить восстановление пути или сам алгоритм.

@Aecttann · 04.06.2014, 22:35 **[ТС]**

да сам алгоритм и код я понимаю, мне нужны идеи насчёт того, как построить путь

@iliya785 · 04.06.2014, 23:03

заведём массив p, где p[i] - вершина из которой мы пришли в вершину i(предок i), изменять значения этого массива будем там же где и улучшаем массив расстояний(у тебя это массив distance, в теле if'a, который на строке 40 нужно дописать p[i] = u). Теперь как восстанавливаем путь: пусть мы находимся в вершине finish(путь из start->finish) теперь перейдём в предка вершины finish(это p[finish]), далее перейдём в предка вершины p[finish](p[p[finish]]) и продолжаем пока не прийдем к старт(если надо могу эту часть кода написать). Остаётся только перевернуть путь (т.к. мы двигались из finish->start). Если есть ещё вопросы пиши, постараюсь ответить

@Aecttann · 04.06.2014, 23:23 **[ТС]**

iliya785,

Сообщение от iliya785

если надо могу эту часть кода написать

не понимаю, что и как сделать в этом цикле)

C++
1
2
3
4
5
6
7
8
9
10
11
12
int p[10];
 
 
    for (i=0; i<V; i++)
 
        if (p[i] = u
            
        
            !visited[i] && GR[u][i] && distance[u]!=max &&
            distance[u]+GR[u][i]<distance[i])
            distance[i]=distance[u]+GR[u][i];
        }

@iliya785 · 04.06.2014, 23:25

C++
1
2
3
4
5
6
7
    for (i=0; i<V; i++)
 
        if (!visited[i] && GR[u][i] && distance[u]!=max &&
            distance[u]+GR[u][i]<distance[i]){
                  distance[i]=distance[u]+GR[u][i];
                  p[i] = u;
           }

также по дефолту заполнить массив p, значениям -1

@Aecttann · 04.06.2014, 23:39 **[ТС]**

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int p[10];
p[0]= -1;
p[1]= -1;
p[2]= -1;
p[3]= -1;
p[4]= -1;
p[5]= -1;
p[6]= -1;
p[7]= -1;
p[8]= -1;
p[9]= -1;
    for (i=0; i<V; i++)
 
        if (!visited[i] && GR[u][i] && distance[u]!=max &&
            distance[u]+GR[u][i]<distance[i]){
                  distance[i]=distance[u]+GR[u][i];
                  p[i] = u;
           }
 
cout << p[i];

@Aecttann · 04.06.2014, 23:46 **[ТС]**

и так по циклу с моей первой точки, до последней, выводится длина пути

@iliya785 · 04.06.2014, 23:49

скинь весь код

@Aecttann · 04.06.2014, 23:52 **[ТС]**

Кликните здесь для просмотра всего текста

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <iostream>
#include <windows.h>
#include <stdio.h>
#include <stdlib.h>
 
using namespace std;
 
const int V=10;
 
void Dejkstra(int GR[V][V], int st)
{
    int max=100;
    int distance[V], count, index, i, u, m=st+1;
    bool visited[V];
 
    for (i=0; i<V; i++)
    {
        distance[i]=max;
        visited[i]=false;
    }
 
    distance[st]=0;
 
    for (count=0; count<V-1; count++)
 
        {
            int min=max;
            for (i=0; i<V; i++)
                if (!visited[i] && distance[i]<=min)
                    {
                        min=distance[i]; index=i;
                    }
 
 
    u=index;
    visited[u]=true;
 
int p[10];
p[0]= -1;
p[1]= -1;
p[2]= -1;
p[3]= -1;
p[4]= -1;
p[5]= -1;
p[6]= -1;
p[7]= -1;
p[8]= -1;
p[9]= -1;
    for (i=0; i<V; i++)
 
        if (!visited[i] && GR[u][i] && distance[u]!=max &&
            distance[u]+GR[u][i]<distance[i]){
                  distance[i]=distance[u]+GR[u][i];
                  p[i] = u;
           }
 
cout << p[i];
 
 
        cout<<"Длина пути Винни до пятака:\n";
 
        //for (i=0; i<V; i++)
            if (distance[i]!=max)
 
 
            cout<<m<<" > "<<V<<" = "<<distance[u] << endl << endl;
            
cout << "Путь из точки А к точке K: " << endl;
 
        if (distance[i-1] > 40 )
        {   Sleep (4000);
            cout << endl << endl << "Может, домой вернуться? :(" << endl << endl; Sleep (2000);
            cout << "Кажется, дождь начинается... :(" << endl;Sleep(1500);}
}
}
 
int main()
 
{
    setlocale(LC_ALL, "Rus");
 
    int start, GR[V][V]=
    {
        {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, 0, 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},
    };
        start = 1;
 
        Dejkstra(GR, start-1);
}

@iliya785 · 05.06.2014, 00:37

Написпл весь код снуля (были серьёзные баги) statrt , finish можешь изменить из main

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
 
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, 0, 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,inf),p(n,-1);
    vector <bool> used(n);
    int start = 0, finish = 3,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;
        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];
        }
    }
}

Добавлено через 5 минут
напиши , что нужно добавить , я тогда сделаю , а то чувствую затянится это надолго

@Aecttann · 05.06.2014, 00:40 **[ТС]**

ну и ну
теперь бы понять что это вообще всё такое, для чего нужны вектора (не знаком с ними))))
и ещё когда меняю значения старт и финиш, оно зацикливается и завершается

также нужно вывести вес пути
он должен быть 60

@iliya785 · 05.06.2014, 00:42

напиши на каких данных циклится

@Aecttann · 05.06.2014, 00:45 **[ТС]**

мне же нужен путь из 1 точки в 10, поэтому:

C++
1
start = 1, finish = 10

@iliya785 · 05.06.2014, 00:53

матрица g[n][n], где n = 10, это значит что можно работать со столбцами и строками размера <= 9 (нумерация с 0). Происходит выход за пределы массива.

Добавлено через 5 минут
а vector в C++ , штука полезная. Вообще это динамический массив.
объявляется он так vector < type (например int) > название.
у него есть несколько конструкторов например:
vector <type> name(size,val) - выделяем массив name на size элеметов и заполняем его val
vector <type> name(size) - выделяем массив name на size элеметов и заполняем дефолтными значениями
vector <type> name - это динамический массив, добавление с помощью метода push_back

@Aecttann · 05.06.2014, 00:56 **[ТС]**

понял

C++
1
int start = 0, finish = 9

выводит неправильный путь:
0-2-6-7-9
а должен быть
0-1-5-6-7-9

@iliya785 · 05.06.2014, 00:59

нашёл баг , теперь всё ок

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#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, 3, 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, 0, 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 = 2, finish = 3,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];
        }
    }
}

Добавлено через 1 минуту
0 - это отсутствие ребра , или налчие ребра нулевой стоимости ?

@Aecttann · 05.06.2014, 01:03 **[ТС]**

то есть по этому пути вес получится 65, а минимальный - 60

Добавлено через 2 минуты
0 - отсутствие ребра

Добавлено через 2 минуты
теперь выводит другой путь - 0-1-3-4-7-9, но вес всё равно 65, а не нужный 60

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@iliya785 24 / 24 / 12 Регистрация: 04.06.2014 Сообщений: 80
	04.06.2014, 02:36
	http://e-maxx.ru/algo/dijkstra , прочитай пункт восстановление пути 0

@Aecttann 6 / 6 / 5 Регистрация: 19.10.2013 Сообщений: 359
	04.06.2014, 03:03 [ТС]
	iliya785, читал, читаю - ничего не выходит 0

@iliya785 24 / 24 / 12 Регистрация: 04.06.2014 Сообщений: 80
	04.06.2014, 22:22
	если всё так плохо , то могу допилить , а также подебажить код. Также могу объяснить восстановление пути или сам алгоритм. 0

@Aecttann 6 / 6 / 5 Регистрация: 19.10.2013 Сообщений: 359
	04.06.2014, 22:35 [ТС]
	да сам алгоритм и код я понимаю, мне нужны идеи насчёт того, как построить путь 0

@iliya785 24 / 24 / 12 Регистрация: 04.06.2014 Сообщений: 80
	04.06.2014, 23:03
	Сообщение было отмечено Aecttann как решение Решение заведём массив p, где p[i] - вершина из которой мы пришли в вершину i(предок i), изменять значения этого массива будем там же где и улучшаем массив расстояний(у тебя это массив distance, в теле if'a, который на строке 40 нужно дописать p[i] = u). Теперь как восстанавливаем путь: пусть мы находимся в вершине finish(путь из start->finish) теперь перейдём в предка вершины finish(это p[finish]), далее перейдём в предка вершины p[finish](p[p[finish]]) и продолжаем пока не прийдем к старт(если надо могу эту часть кода написать). Остаётся только перевернуть путь (т.к. мы двигались из finish->start). Если есть ещё вопросы пиши, постараюсь ответить 0

@Aecttann 6 / 6 / 5 Регистрация: 19.10.2013 Сообщений: 359
	04.06.2014, 23:46 [ТС]
	и так по циклу с моей первой точки, до последней, выводится длина пути 0

@iliya785 24 / 24 / 12 Регистрация: 04.06.2014 Сообщений: 80
	04.06.2014, 23:49
	скинь весь код 0

@Aecttann 6 / 6 / 5 Регистрация: 19.10.2013 Сообщений: 359
	05.06.2014, 00:40 [ТС]
	ну и ну теперь бы понять что это вообще всё такое, для чего нужны вектора (не знаком с ними)))) и ещё когда меняю значения старт и финиш, оно зацикливается и завершается также нужно вывести вес пути он должен быть 60 0

@iliya785 24 / 24 / 12 Регистрация: 04.06.2014 Сообщений: 80
	05.06.2014, 00:42
	напиши на каких данных циклится 0

@iliya785 24 / 24 / 12 Регистрация: 04.06.2014 Сообщений: 80
	05.06.2014, 00:53
	матрица g[n][n], где n = 10, это значит что можно работать со столбцами и строками размера <= 9 (нумерация с 0). Происходит выход за пределы массива. Добавлено через 5 минут а vector в C++ , штука полезная. Вообще это динамический массив. объявляется он так vector < type (например int) > название. у него есть несколько конструкторов например: vector <type> name(size,val) - выделяем массив name на size элеметов и заполняем его val vector <type> name(size) - выделяем массив name на size элеметов и заполняем дефолтными значениями vector <type> name - это динамический массив, добавление с помощью метода push_back 1

@Aecttann 6 / 6 / 5 Регистрация: 19.10.2013 Сообщений: 359
	05.06.2014, 01:03 [ТС]
	то есть по этому пути вес получится 65, а минимальный - 60 Добавлено через 2 минуты 0 - отсутствие ребра Добавлено через 2 минуты теперь выводит другой путь - 0-1-3-4-7-9, но вес всё равно 65, а не нужный 60 0

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

Решение