Алгоритм Дейкстры

@Leonsmoke · Регистрация: 26.02.2018

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

Всем доброго дня! Столкнулся с проблемой, никак не могу понять, как лучше реализовать алгоритм Дейкстры на с++.
У меня есть двумерный массив A[x][y] в котором записаны расстояния, между вершинами x и y графа. Можете подсказать, как мне действовать и от чего плясать? Заранее спасибо

@LegionK · 27.05.2018, 11:34

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

двумерный массив A[x][y] в котором записаны расстояния, между вершинами x и y графа

Это же матрица смежности твоего графа?
Сначала можно посмотреть темы снизу или просто загуглить, все это давно есть

@LegionK · 27.05.2018, 11:49

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
#include <iostream>
#include <iomanip>
 
using namespace std;
 
int main()
{
    int big_num(10000);
    int matrix[5][5] = {{0,5,12,0,0},       // матрица смежности моего графа, сам он на фотке
                        {5,0,4,0,1},
                        {12,4,0,2,0},
                        {0,0,2,0,5},
                        {0,1,0,5,0}};
 
    int pos[5],node[5],min(0),index_min(0);
    for(int i = 0;i<5;++i){     // заполняем путь к вершине большими числами, желательно взять биг_нам ещё больше, но и так ок.
        pos[i] = big_num;       // а все вершины помечаем как "непройденные"
        node[i] = 0;
    }
    for(int i = 0;i<5;++i){     // вывод матрицы
        for(int j = 0;j<5;++j){
            cout << setw(4) << matrix[i][j];
        }
        cout << "\n";
    }
    pos[2] = 0;                // назначаем какую-то вершину началом алгоритма, узлом ( или так не говорят, хз)
    for(int i = 0;i<4;++i){    // основной цикл
        min = big_num;
        for(int j = 0;j<5;++j){     // находим вершину с минимальным к ней расстоянием, на первом шаге это будет узел
            if(!node[j] && pos[j] < min){
                min = pos[j];
                index_min = j;
            }
        }
        node[index_min] = true;   // помечаем выбранную вершину как пройденную
        for(int j = 0;j<5;++j){   // цикл, в котором мы даем всем вершинам, смежным с выбранной вес пути к ней
            if(!node[j] && matrix[index_min][j] > 0 && pos[index_min] != big_num && pos[index_min] + matrix[index_min][j] < pos[j]){
                pos[j] = pos[index_min] + matrix[index_min][j];
            } // условие такое, если эта вершина не пройденная и она смежна с выбранной и если сумма веса выбранной вершины и ребра к текущей будет меньше, чем
        }     // вес текущей на данный момент, то  - меняем значение веса текущей вершины.
    }
    cout << pos[0] << "\n"; // теперь у нас в pos минимальные расстояния от выбранного узла к любой другой вершине
 
    cout << endl;
    return 0;
}

Я в этом не мастер-фломастер, но попробую - вот мой вариант реализации, если гуглить лень

@Leonsmoke · 27.05.2018, 13:17 **[ТС]**

Спасибо огромное! Вы мне очень помогли

Добавлено через 1 час 16 минут

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

Я в этом не мастер-фломастер, но попробую - вот мой вариант реализации, если гуглить лень

А можно еще вопросик, как мне найти сам путь? По вершинам. То есть нужно найти кратчайший путь от 1 до 5, и нужно чтобы вывело например 135

@Ромаха · 27.05.2018, 14:33

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

А можно еще вопросик, как мне найти сам путь? По вершинам. То есть нужно найти кратчайший путь от 1 до 5, и нужно чтобы вывело например 135

Либо хранить. Вверху есть строчку p[j] = p[j]+что-то там
Заводите еще один vector<int> parent(n, -1);
И после этой строки вставляете parent[j] = i;

Вывод тогда будет таким

Code
1
2
3
4
while(pos != -1) {
   cout << pos << " ";
   pos = parent[pos];
}

Либо искать. Давайте представим, что граф неориентированный. Тогда это будет примерно так

Code
1
2
3
4
5
6
7
8
9
cout << pos << " ";
while(pos != №вершины от которой ищем) {
    for(int i = 0; i < n; i++)
       if (p[pos]==p[i]+matrix[pos][i]) {
          cout << i << " ";
          pos = i;
          break;
       }
}

@Leonsmoke · 28.05.2018, 13:34 **[ТС]**

Сообщение от Ромаха

cout << pos << " ";
while(pos != №вершины от которой ищем) {
for(int i = 0; i < n; i++)
if (p[pos]==p[i]+matrix[pos][i]) {
cout << i << " ";
pos = i;
break;
}
}

а что здесь за массив p?

Добавлено через 22 часа 29 минут
Вот что у меня получилось... ищет короткие пути из любой вершины в любую, но вот как сам путь найти я, хоть убейте, не допру

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
for (i = 0; i<kolvo; i++)
    {
        distance[i] = INT_MAX; visited[i] = false;
    }
    distance[otkuda] = 0;
    for (count = 0; count<kolvo; count++)
    {
        int min = INT_MAX;
        for (i = 0; i<kolvo; i++)
            if (!visited[i] && distance[i] <= min)
            {
                min = distance[i]; index = i;
            }
        u = index;
        visited[u] = true;
        for (i = 0; i < kolvo; i++)
        {
            if (!visited[i] && dlins[u, i] && distance[u] != INT_MAX &&
                (distance[u] + dlins[u, i]) < distance[i])
            {
                distance[i] = distance[u] + dlins[u, i];
            }
            
        }
        
    }

@LegionK · 28.05.2018, 15:32

Leonsmoke, цитата с интернета : разумеется, обычно нужно знать не только длины кратчайших путей, но и получить сами пути. Покажем, как сохранить информацию, достаточную для последующего восстановления кратчайшего пути из s до любой вершины. Для этого достаточно так называемого массива предков: массива p[], в котором для каждой вершины v != s хранится номер вершины p[v], являющейся предпоследней в кратчайшем пути до вершины v. Здесь используется тот факт, что если мы возьмём кратчайший путь до какой-то вершины v, а затем удалим из этого пути последнюю вершину, то получится путь, оканчивающийся некоторой вершиной p[v], и этот путь будет кратчайшим для вершины p[v]. Итак, если мы будем обладать этим массивом предков, то кратчайший путь можно будет восстановить по нему, просто каждый раз беря предка от текущей вершины, пока мы не придём в стартовую вершину s — так мы получим искомый кратчайший путь, но записанный в обратном порядке.

Осталось понять, как строить этот массив предков. Однако это делается очень просто: при каждой успешной релаксации, т.е. когда из выбранной вершины v происходит улучшение расстояния до некоторой вершины to, мы записываем, что предком вершины to является вершина v:

p[to] = v

Добавлено через 1 час 33 минуты
Leonsmoke, если на примере сообщения выше, первого способа Ромаха и моего кода из моего же, собсна,первого ответа, то как-то так :

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
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main()
{
    vector<int> parent(5,-1);    // объявили и сразу заполнили -1-цами в кол-ве 5 штук
    int big_num(10000);
    int matrix[5][5] = {{0,5,12,0,0},
                        {5,0,4,0,1},
                        {12,4,0,2,0},
                        {0,0,2,0,5},
                        {0,1,0,5,0}};
 
    int pos[5],node[5],min(0),index_min(0);
    for(int i = 0;i<5;++i){
        pos[i] = big_num;
        node[i] = 0;
    }
    for(int i = 0;i<5;++i){
        for(int j = 0;j<5;++j){
            cout << setw(4) << matrix[i][j];
        }
        cout << "\n";
    }
    pos[0] = 0;            // наш узел
    cout << "\n";
    for(int i = 0;i<4;++i){
        min = big_num;
        for(int j = 0;j<5;++j){
            if(!node[j] && pos[j] < min){
                min = pos[j];
                index_min = j;
            }
        }
        node[index_min] = true;
        for(int j = 0;j<5;++j){
            if(!node[j] && matrix[index_min][j] > 0 && pos[index_min] != big_num && pos[index_min] + matrix[index_min][j] < pos[j]){
                pos[j] = pos[index_min] + matrix[index_min][j];
                parent.at(j) = index_min;    // запоминаем предка вершины j
            }
        }
    }
    int n(0);
    cout << "\nnumber of top? : ";
    cin >> n;
 
    vector<int>temp;     // n - 1, так как не забываем про индексацию
    for(int i = n-1;i != -1;i = parent.at(i))temp.push_back(i+1);   // а все что здесь делается  описано в справке,которую я те кинул
    reverse(temp.begin(),temp.end());
    for(int i = 0;i<temp.size();++i)cout << temp.at(i) << " ";
 
    cout << "\nWeight : " << pos[n-1] << "\n";
 
    cout << endl;
    return 0;
}

P.s Граф с той же фотографии

@Leonsmoke · 28.05.2018, 18:00 **[ТС]**

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

Leonsmoke, если на примере сообщения выше, первого способа Ромаха и моего кода из моего же, собсна,первого ответа, то как-то так :

Разобрался! Наконец-то до меня дошло)) Спасибо Вам огромное

@Toshikshik · 09.12.2019, 18:54

Здравствуйте, подскажите, а как изменить код так, чтобы путь выводился для каждой вершины ?

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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
#include <iostream>
#include <vector>// для вектора
#include <algorithm>// для работы с алгоритмами (для reserve)
#include <fstream> //для вывода из файла
 
using namespace std;
 
int main()
{
system ("chcp 1251 ");
cout<<"Программа, выполняющая алгоритм Дейкстры"<<endl;
int a=1;
int menu;
int row;//кол-во вершин
int column;//кол-во вершин
int **matrix;
matrix= new int*[column];
 
int i,j;
 
while(a==1){
    cout<<"Выберите действие:"<<endl;
    cout<<"1.Ввести граф с клавиатуры"<<endl;
    cout<<"2.Ввести граф из файла  "<<endl;
    cout<<"3.Результат действия алгоритма до конкретной вершины"<<endl;
    cout<<"0.Завершить программу "<<endl;
    cout<<"Действие номер: ";
    cin>>menu;  
    
    
switch(menu){
    case 0:{
        a==0;
        delete[]matrix;
        break;
    }
    case 1:{
        cout<<"Введите количество вершин:"<<endl;
            cin>>column;
            row=column;
            matrix= new int*[row];
            for(int i=0; i<row; i++){
                matrix[i]= new int[column];
                matrix[row][column];
            }
            cout<<" "<<endl;
            cout<<"Сейчас вы заполняете матрицу с длинами ребер \n";
            for(int i = 0; i < column ; i++) { //заполнение
                for(int j = 0; j < row; j++){
                    cout <<"Введите элемент матрицы" << "[" << i << "][" << j << "]: ";
                    cin >> matrix[i][j];        
                }
            }
    cout << endl;
    cout<<"Введенная матрица:"<<endl;
        for(int i = 0; i < column ; i++) { //вывод
                for(int j = 0; j < row; j++){
                    cout << matrix[i][j]<<" ";     
                }
                cout<<endl;
            }
 
        
        break;
    }
    case 2:{
        cout << "Введенная матрица: "<<endl;
 
    ifstream in("matrix.txt");
    if (in.is_open()){
        int count = 0;//cчетчик
        int temp;
 
    while (!in.eof()){
        in >> temp;
        count++;
        }
 
    in.seekg(0, ios::beg);
    in.clear();
 
    int count_space = 0;
    char symbol;
    while (!in.eof()){
            
        in.get(symbol);
        if (symbol == ' ') count_space++;
        if (symbol == '\n') break;
    }
    
    in.seekg(0, ios::beg);
    in.clear();
 
     row = count / (count_space + 1);
     column = count_space + 1;
        
    for ( i = 0; i<row; i++) matrix[i] = new int[column];
 
    for ( i = 0; i < column; i++)
    for ( j = 0; j < column; j++)
    in >> matrix[i][j];
 
    for ( i = 0; i < column; i++){
        for ( j = 0; j < column; j++)
            cout << matrix[i][j]<<" ";
            cout << "\n";
    }
 
    in.close();
        
    }
    cout<<endl;
        break;
    }
    case 3:{
    int big_num=INT_MAX;//бесконечно большое число 
 
    int pose[row];//посещенные
    bool nepose[row];//непосещенные
    int min=0;
    int index_min=0;
    
            
        for(int i = 0;i<row;++i){ //заполняем массив посещенных бесконечно большими числами, непосещенные(временно присоед.) заполняются 0
 
            pose[i] = big_num;
            nepose[i] = false;
            parent[i] = -1;
        }
        cout << "Введенная матрица: "<<endl;
         for(int i = 0; i<row;++i){//вывод матрицы
            for(int j = 0;j<row;++j){
                cout << matrix[i][j]<<" ";
        }
        cout << "\n";
     }
    cout<<"Какую вершину считать узлом(корнем)?";
    cin>>pose[0];
    nepose[0]=true;
    
    
    cout << "\n";
    for(int i = 0; i<row-1;++i){
        min = big_num;
        
        for(int j = 0;  j<row-1;  ++j){
            if(!nepose[j] && pose[j] < min){// 
                min = pose[j];//минимальное значение вершины
                index_min = j;//индекс "минимальной" вершины
            }
        }
      
        nepose[j] = true;
        
        for(int j = 0;j<row;++j){
            if(!nepose[j] && matrix [index_min][j] > 0 && pose [index_min] != big_num && pose [index_min] + matrix [index_min][j] < pose[j]){
                pose [j] = pose [index_min] + matrix [index_min][j];
            }
        }
        
    }
    
  for(int i =0; i< row-1;i++ ){
 
    cout<<"Для вершины "<<i+1<<":"<<endl; 
    cout<<"Номера вершин пути:"<<endl;
    //ТУТ ДОЛЖЕН БЫТЬ ВЫВОД ПУТИ              
                            
                            
                            
                            
                            
                                
 cout << "\nКратчайший путь равен: " << pose[i+1] << "\n";
    cout << endl;
    }
  
    break;
    }
}   
}
    return 0;
}

Новые блоги и статьи Все статьи Все блоги /
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 . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@Leonsmoke 0 / 0 / 0 Регистрация: 26.02.2018 Сообщений: 17

	Алгоритм Дейкстры 27.05.2018, 11:12. Показов 76083. Ответов 8 Метки нет (Все метки) Всем доброго дня! Столкнулся с проблемой, никак не могу понять, как лучше реализовать алгоритм Дейкстры на с++. У меня есть двумерный массив A[x][y] в котором записаны расстояния, между вершинами x и y графа. Можете подсказать, как мне действовать и от чего плясать? Заранее спасибо 0

Алгоритм Дейкстры

Решение