Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 31, средняя оценка - 4.61
Iworb
анимешник++
 Аватар для Iworb
93 / 60 / 2
Регистрация: 03.11.2009
Сообщений: 411
15.12.2010, 20:38     Алгоритм Дейкстры #1
День добрый!
Есть игровое поле 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;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.12.2010, 20:38     Алгоритм Дейкстры
Посмотрите здесь:

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

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
QVO
 Аватар для QVO
636 / 447 / 32
Регистрация: 26.10.2010
Сообщений: 1,261
Записей в блоге: 4
Завершенные тесты: 2
08.11.2011, 22:26     Алгоритм Дейкстры #2
Алгоритм Дейкстры поиска кратчайшего пути.
Пусть задан простой неориентированный граф 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
3 / 4 / 0
Регистрация: 18.11.2009
Сообщений: 405
05.05.2013, 12:02     Алгоритм Дейкстры #3
Мне известно несколько реализаций алг.Дейкстры, отличающиеся структурами используемых данных.
На входе у них как правило матрица смежности (весов) Отличаются использованием структур при реализации - списков, очередей, массивов. Все не сравнивал,но простейшая с массивами имеет некоторый недостаток -находит только одно минимальное дерево. Т.е возможны случаи когда в неориентированном графе на вход проге даешь
nach=i fin=j получаешь некий путь, затем меняешь местами nach=j fin=i и получаешь совсем другой путь
(правда их длины совпадают). Интересна модификация алгоритма выводящие все кратчайшие пути от i до j если их несколько)
Yandex
Объявления
05.05.2013, 12:02     Алгоритм Дейкстры
Ответ Создать тему

Метки
граф, дейкстра, Игра
Опции темы

Текущее время: 09:09. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru