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

Iworb

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

Iworb

Алгоритм Дейкстры поиска кратчайшего пути. Пусть задан простой неориентированный граф 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] – постоянный вес.
//---------------------------------------------------------------------------
//Алгоритм Дейкстры.поиска кратчайшего пути
#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.*/
 
//---------------------------------------------------------------------------


Iworb

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