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

@Iworb · Регистрация: 03.11.2009

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

День добрый!
Есть игровое поле M*M. Количесво графов - N.
Есть матрица смежности этого игрового поля.
Получить элемент матрицы можно по GetTab(i,j)
Помогите написать алгоритм Дейкстры от вершины s до вершины t, при этом сохраняя список посещенных вершин в массив или вектор.
Вот, что у меня есть на данный момент(пока без алгоритма Дейкстры):

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
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <Windows.h>
#include <GL\glut.h>
#define M 4 //размер поля
#define N M*M //матрица смежности
#define BIG N //большое число и фоновый элемент
using namespace std;
/*----------------------------------------
--row - хранит номер строки разреженной матрицы
--col - хранит номер стролбца разреженной матрицы
--appr - значение
--leap - номера вершин с препятствиями
--s - исходная вершина
--t - конечная вершина
----------------------------------------*/
int *row, *col, *adj_row, *adj_col;
int s=N-1, t=0;
float *appr;
bool *adj_appr;
vector<int> leap;
float GetTab(int i, int j);
bool adj_GetTab(int i, int j);
 
void change(int *a, int *b)
{
    int c;
    c=*a;
    *a=*b;
    *b=c;
}
 
void unique(vector<int> p)
{
    for(int i=0;i<p.size();i++)
    {
        for(int j=i;j<p.size();j++)
        {
            if(p[i]==p[j]||(!p[j])||(p[j]==M-1))
            {
                p.erase(p.begin()+j);
                j--;
            }
        }
    }
    for(int i=0;i<leap.size();i++)
    {
        for(int j=0;j<p.size();j++)
        {
            if(leap[i]==p[j])
            {
                p.erase(p.begin()+j);
                j--;
            }
        }
    }
}
 
void _random_snag_generation()
{
    int bi=(M-3)*rand()/RAND_MAX+1,bj=(M-3)*rand()/RAND_MAX+1, max_num_p=(M-2)*(M-2), num=(max_num_p-1)*rand()/RAND_MAX+1, i, j, l, u, k=1;
    //max_num_p - максимальное число точек-препятствий
    leap.clear();
    leap.push_back(bi*M+bj);
    while(k<num)
    {
        vector<int> temp;
        temp.clear();
        for(l=0;l<leap.size();l++)
        {
            i=(leap[k-1]-leap[k-1]%M)/M;
            j=leap[k-1]%M;
            if(((i-1)*M+j>=0)&&(i+j)) temp.push_back((i-1)*M+j);     //top
            if(((i*M+j-1)%M!=M-1)&&(i+j)) temp.push_back(i*M+j-1);   //left
            if(((i+1)*M+j<=N)&&(i+j!=N-1)) temp.push_back((i+1)*M+j);     //bottom
            if(((i*M+j+1)%M)&&(i+j!=N-1)) temp.push_back(i*M+j+1);        //right
        }
        unique(temp);
        leap.push_back(temp[temp.size()*rand()/RAND_MAX]);
        k++;
    }
}
 
void PutTab(int k, int i, int j, float value)
{
    row[k]=i;
    col[k]=j;
    appr[k]=value;
}
 
void adj_PutTab(int k, int i, int j, bool value)
{
    adj_row[k]=i;
    adj_col[k]=j;
    adj_appr[k]=value;
}
 
float GetTab(int i, int j)
{
    if(i>j) change(&i,&j);
    int n=0,m,xi;
    while(row[n]<i) n++;
    m=n;
    while(row[m]<=i) m++;
    for(xi=n;xi<m;xi++)
        if(col[xi]==j)
            return appr[xi];
    return BIG;
}
 
bool adj_GetTab(int i, int j)
{
    if(i>j) change(&i,&j);
    int n=0,m,xi;
    while(adj_row[n]<i) n++;
    m=n;
    while(adj_row[m]<=i) m++;
    for(xi=n;xi<m;xi++)
        if(adj_col[xi]==j)
            return adj_appr[xi];
    return false;
}
 
void Init()
{
        //Инициализация матрицы смежности с препятствиями
        _random_snag_generation();
        int m=0,i,j,k; //m - кол-во нефоновых
        bool f;
        for(i=0;i<N;i++)
        {
            f=1;
            for(k=0;k<leap.size();k++)
                if(i==leap[k])
                    f=0;
            if(!f) continue;
            for(j=i;j<N;j++)
            {
                f=1;
                for(k=0;k<leap.size();k++)
                    if(j==leap[k])
                        f=0;
                if(!f) continue;
                if(i==j)
                {
                    PutTab(m,i,j,0);
                    adj_PutTab(m,i,j,1);
                    m++;
                }
                if(((j-i==1)&&(i%M!=M-1))||(j-i==M))
                {
                    PutTab(m,i,j,1);
                    adj_PutTab(m,i,j,1);
                    m++;
                }
                if(((j-i==M-1)&&(j%M!=M-1))||((j-i==M+1)&&(j%M)))
                {
                    PutTab(m,i,j,1.5);
                    adj_PutTab(m,i,j,1);
                    m++;
                }
            }
        }
}
 
void Print_ms(int f=1)
{
    for(int i=0;i<N;i++)
    {
       for(int j=0;j<N;j++)
       {
           if(GetTab(i,j)!=BIG)
               cout<<setw(3)<<(f?GetTab(i,j):adj_GetTab(i,j))<<" ";
           else
               cout<<setw(3)<<"M"<<" ";
       }
       cout<<endl;
    }
}
 
void display()
{
    glClear(GL_COLOR_BUFFER_BIT);
    //Поле
    const int step=600/M;
    glBegin(GL_QUADS);
    for(int i=0;i<M;i++)
        for(int j=0;j<M;j++)
        {
            bool f=0;
            for(int k=0;k<leap.size();k++)
                if(i==leap[k]%M&&j==(leap[k]-leap[k]%M)/M) f=1;
            if(f) glColor3f(0,0,0);
            else
            {   
                glColor3f(1,1,1);
                if(i==t%M&&j==(t-t%M)/M) glColor3f(1,0,0);
                if(i==s%M&&j==(s-s%M)/M) glColor3f(0,0,1);
            }
            const int x=i*step;
            const int y=j*step;
            glVertex2f(x,y);
            glVertex2f(x+step,y);
            glVertex2f(x+step,y+step);
            glVertex2f(x,y+step);
        }
    glEnd();
    //-----------
    glFlush();                                  
}
 
int main(int argc, char** argv)
{
   //srand(GetTickCount());
    srand(0);
   appr=new float[(M+1)*N]; row=new int[(M+1)*N]; col=new int[(M+1)*N];
   adj_appr=new bool[(M+1)*N]; adj_row=new int[(M+1)*N]; adj_col=new int[(M+1)*N];
   leap.clear();
   Init();
   glutInit(&argc, argv);                       
   glutInitDisplayMode (GLUT_SINGLE|GLUT_RGB); 
   glutInitWindowSize(600,600);             
   glutInitWindowPosition(0,0);                 
   glutCreateWindow("Test");                    
   glClearColor(1.0, 1.0, 1.0, 1.0);            
   glMatrixMode(GL_PROJECTION);                 
   glLoadIdentity();                        
   gluOrtho2D(0, 600, 600, 0);  
   glutDisplayFunc(display);                
   glutMainLoop();                              
   return 0;
   delete appr; delete row; delete col;
   delete adj_appr; delete adj_row; delete adj_col;
}

@QVO · 08.11.2011, 22:26

Алгоритм Дейкстры поиска кратчайшего пути.
Пусть задан простой неориентированный граф G = (V, E), как конечное множество вершин V и множество E неупорядоченных пар {vi, vj} – ребер. Каждому ребру предписано действительное число a[i][j] > 0, которое называется длиной этого ребра. Требуется найти кратчайший путь между заданными вершинами s и q, то есть такую последовательность вершин u1,u2,…,un, что u1=s, un=q, {ui, ui+1}E для всех 1  i  n-1, и сумма длин ребер {ui, ui+1} минимальна. Задача решается с помощью алгоритма Дейкстры:
1. Каждой вершине припишем временный вес t (vi) = . Положим t (s) = 0 и далее t (s) изменяться не будет, т.е. t (s) – постоянный вес вершины s. Положим v = s.
2. Для всех вершин u = vi, смежных с v, имеющих временный вес, изменяем вес по формуле .
3. Устанавливаем постоянный вес той вершины u, которая имеет наименьший временный вес. Положим v = u. Если v = q, то t (v) – длина кратчайшего пути из s в q. Если v  q, то переходим к шагу 2.
В результате работы алгоритма получим длину кратчайшего пути из s в q. Чтобы найти вершину и ребра, составляющие этот путь, нужно определить массив h[|V|], где h[v] – вершина, предшествующая вершине v на кратчайшем пути, а в шаге 2 добавить операцию h[u] = v, в случае, когда t (u) > t (v)+a[v][u].
Можно получить кратчайшие пути от s ко всем другим вершинам, изменив условие остановки. Вычисления заканчиваются, когда все веса становятся постоянными.
В тексте программы веса вершин записываются в массив t [ ]. Для обозначения того, что для вершины v вес t [v] постоянный, вводится массив x[ ]. Равенство x[v]=1 будет означать, что t [v] – постоянный вес.

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
//---------------------------------------------------------------------------
//Алгоритм Дейкстры.поиска кратчайшего пути
#include <vcl.h>
#include <iostream.h>
#include <conio.h>
#pragma hdrstop
#pragma argsused
 
#define VERTEXES 6  //Число вершин в графе
 
int v;
int main(int argc, char* argv[])
{
   clrscr();
   int infinity=1000;                     // Бесконечность
   int p= VERTEXES;             // Количество вершин в графе
   int a[VERTEXES][VERTEXES]={ 0,1,0,0,1,3,  // Матрица смежности графа
                               1,0,5,0,0,1,
                               0,5,0,5,20,1,
                                 0,0,5,0,3,2,
                               1,0,20,3,0,10,
                               3,1,1,2,10,0  };
 
   // Будем искать путь из вершины s в вершину g
   int s;                   // Номер исходной вершины
   int g;                   // Номер конечной вершины
   cout<<"Введите s: ";      // Номер может изменяться от 0 до p-1
   cin>>s;
   cout<<"Введите g: ";
   cin>>g;
   int x[VERTEXES]; //Массив, содержащий единицы и нули для каждой вершины,
                  // x[i]=0 - еще не найден кратчайший путь в i-ю вершину,
                  // x[i]=1 - кратчайший путь в i-ю вершину уже найден
   int t[VERTEXES];  //t[i] - длина кратчайшего пути от вершины s в i
   int h[VERTEXES];  //h[i] - вершина, предшествующая i-й вершине
                 // на кратчайшем пути
 
   // Инициализируем начальные значения массивов
   int u;           // Счетчик вершин
   for (u=0;u<p;u++)
   {
      t[u]=infinity; //Сначала все кратчайшие пути из s в i 
    //равны бесконечности
      x[u]=0;        // и нет кратчайшего пути ни для одной вершины
   }
   h[s]=0; // s - начало пути, поэтому этой вершине ничего не предшествует
   t[s]=0; // Кратчайший путь из s в s равен 0
   x[s]=1; // Для вершины s найден кратчайший путь
   v=s;    // Делаем s текущей вершиной
   
   while(1)
   {
      // Перебираем все вершины, смежные v, и ищем для них кратчайший путь
      for(u=0;u<p;u++)
      {
         if(a[v][u]==0)continue; // Вершины u и v несмежные
         if(x[u]==0 && t[u]>t[v]+a[v][u]) //Если для вершины u еще не 
    //найден кратчайший путь
                // и новый путь в u короче чем 
    //старый, то
         {
            t[u]=t[v]+a[v][u];  //запоминаем более короткую длину пути в
    //массив t и
            h[u]=v; //запоминаем, что v->u часть кратчайшего 
    //пути из s->u
         }
      }
 
      // Ищем из всех длин некратчайших путей самый короткий
      int w=infinity;  // Для поиска самого короткого пути
      v=-1;            // В конце поиска v - вершина, в которую будет 
                       // найден новый кратчайший путь. Она станет 
                       // текущей вершиной
      for(u=0;u<p;u++) // Перебираем все вершины.
      {
         if(x[u]==0 && t[u]<w) // Если для вершины не найден кратчайший 
                               // путь и если длина пути в вершину u меньше
                               // уже найденной, то
         {
            v=u; // текущей вершиной становится u-я вершина
            w=t[u];
         }
      }
      if(v==-1)
      {
         cout<<"Нет пути из вершины "<<s<<" в вершину "<<g<<"."<<endl;
         break;
      }
      if(v==g) // Найден кратчайший путь,
      {        // выводим его
         cout<<"Кратчайший путь из вершины "<<s<<" в вершину "<<g<<":";
       u=g;
       while(u!=s)
         {
            cout<<" "<<u;
            u=h[u];
         }
         cout<<" "<<s<<". Длина пути - "<<t[g];
       break;
      }
      x[v]=1;
   }
   getch();
}
/*Программа запрашивает вершины s и q и выводит кратчайший путь. Например, после ввода s = 3, q = 6, программа выводит 
 
Нет пути из вершины 3 в вершину 6. 
 
После ввода s = 0, q = 2 программа выводит 
 
Кратчайший путь из вершины 0 в вершину 2: 2 5 1 0. Длина пути = 3.*/
 
//---------------------------------------------------------------------------

@eugrita · 05.05.2013, 12:02

Мне известно несколько реализаций алг.Дейкстры, отличающиеся структурами используемых данных.
На входе у них как правило матрица смежности (весов) Отличаются использованием структур при реализации - списков, очередей, массивов. Все не сравнивал,но простейшая с массивами имеет некоторый недостаток -находит только одно минимальное дерево. Т.е возможны случаи когда в неориентированном графе на вход проге даешь
nach=i fin=j получаешь некий путь, затем меняешь местами nach=j fin=i и получаешь совсем другой путь
(правда их длины совпадают). Интересна модификация алгоритма выводящие все кратчайшие пути от i до j если их несколько)

@AlexKrutoy · 23.06.2019, 12:08

QVO, Добрый день.
Как в ваш код Алгоритм Дейкстры поиска кратчайшего пути, добавить функцию? Такую чтобы граф задавался чтением файла txt матрицей весов.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

@eugrita 5 / 6 / 4 Регистрация: 18.11.2009 Сообщений: 661
	05.05.2013, 12:02
	Мне известно несколько реализаций алг.Дейкстры, отличающиеся структурами используемых данных. На входе у них как правило матрица смежности (весов) Отличаются использованием структур при реализации - списков, очередей, массивов. Все не сравнивал,но простейшая с массивами имеет некоторый недостаток -находит только одно минимальное дерево. Т.е возможны случаи когда в неориентированном графе на вход проге даешь nach=i fin=j получаешь некий путь, затем меняешь местами nach=j fin=i и получаешь совсем другой путь (правда их длины совпадают). Интересна модификация алгоритма выводящие все кратчайшие пути от i до j если их несколько) 0

@AlexKrutoy 0 / 0 / 0 Регистрация: 14.06.2019 Сообщений: 2
	23.06.2019, 12:08
	QVO, Добрый день. Как в ваш код Алгоритм Дейкстры поиска кратчайшего пути, добавить функцию? Такую чтобы граф задавался чтением файла txt матрицей весов. 0