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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 31, средняя оценка - 4.61
Iworb
анимешник++
93 / 60 / 2
Регистрация: 03.11.2009
Сообщений: 413
#1

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

15.12.2010, 20:38. Просмотров 3913. Ответов 2

День добрый!
Есть игровое поле 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++
Лабиринт задается матрицей, где 0 стены, 1 проходы, s - начальная вершина, f - конечная. Лабиринт считывается из файла. Не могу сообразить,...

Работа с графами. Алгоритм Дейкстры - C++
Может у кого есть исходник для реализации алгоритма Дейкстры, когда граф представлен не матрицей смежности, а списком рёбёр. Просто есть...

Вывод пути (алгоритм Дейкстры) - C++
Реализация алгоритма Дейкстра. В массиве distance - найденные кратчайшие пути, visited - логический, для хранения информации о...

Вставить алгоритм Дейкстры в программу - C++
Вот рабочая программа которая находит кратчайшый путь по алгоритму Дейкстры А вот моя в которую нужно вставить алгоритм ...

Алгоритм Дейкстры с рандомной матрицей - C++
Необходимо, чтобы при запуске программы создавалась рандомная матрица 9x9 в которой: рандом генерируется по всей матрице, кроме главной...

Алгоритм Дейкстры (цена на бензин) - C++
Думаю с этой задачей многие сталкивались :) Входные данные Во входном файле INPUT.TXT записано сначала число N (1 ≤ N ≤ 100), затем...

Алгоритм Дейкстры. Консольное приложение - C++
Помогите, помогите, помогите кто чем может, пожалуйста!.. срочно пипец вообще как нужна программа на плюсах, реализующая алгоритм Дейкстры...

Алгоритм Дейкстры (часть кода есть) - C++
Здравствуйте! Нужно реализовать на С++ такую консольную программу: 1. Задается массив размерности n; 2. Найти максим. j такой, что a...

Алгоритм Дейкстры неправильно выводит путь - C++
вот прога, но она неправильно выводит путь((( #include&lt;iostream&gt; #include&lt;fstream&gt; #include&lt;conio.h&gt; #include&lt;locale.h&gt; ...

Алгоритм Дейкстры в связном списке + файлы. - C++
Задача такова : Имеются n городов. Некоторые из них соединены дорогами известной длины. Найти кратчайшие маршруты из заданного города в...

Требуется реализовать алгоритм Дейкстры начинающему программисту - C++
Ребята огромная просьба помочь с программой. Условия следушие-реализовать алгоритм Дейкстры на С++. Я сидел парился и смог только часть...

Задача на алгоритм Дейкстры (как лучше хранить информацию?) - C++
Доброго времени суток. Есть задача: Есть идея хранить входные данные след. образом: Выделить в памяти 2-х матрицы(Tab1 и Tab2...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru