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

Алгоритм Дейкстры для лабиринта - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.92
Cee K
1 / 1 / 0
Регистрация: 05.04.2012
Сообщений: 46
11.07.2012, 17:27     Алгоритм Дейкстры для лабиринта #1
Лабиринт задается матрицей, где 0 стены, 1 проходы, s - начальная вершина, f - конечная. Лабиринт считывается из файла. Не могу сообразить, как алгоритм Дейкстры для графов применить для лабиринта( как посчитать количество вершин и ребер и их длины
s 1 1 0 1
0 1 1 0 1
1 1 1 1 0
0 1 0 1 1
0 1 1 0 f

подскажите,пожалуйста
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.07.2012, 17:27     Алгоритм Дейкстры для лабиринта
Посмотрите здесь:

Алгоритм Дейкстры C++
Алгоритм Дейкстры C++
C++ Алгоритм Дейкстры
Алгоритм Дейкстры С++ C++
Алгоритм обхода лабиринта C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Lel'ka
8 / 8 / 2
Регистрация: 10.07.2012
Сообщений: 38
11.07.2012, 17:37     Алгоритм Дейкстры для лабиринта #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
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
//Диаметр графа (Алгоритм Дейкстры)
int diam(struct graph *A){
   int n=vertice(A);
   int max=0;
   int x[n]; //Массив, содержащий единицы и нули для каждой вершины, x[i]=0 - еще не найден длиннейший путь в i-ю вершину, x[i]=1 - длиннейший путь в i-ю вершину уже найден
   int t[n];  //t[i] - длина длинейшего пути от вершины s в i
   int s;                   // Номер исходной вершины
   int g;                   // Номер конечной вершины (в нашем случае перебираются все)
   for (s=1; s<n-1; s++){
       for (g=s+1; g<n; g++){
           for (int u=0; u<n; u++){
               t[u]=0;        //Сначала все длиннейшие пути из s в i равны нулю
               x[u]=0;        // и нет длиннейшего пути ни для одной вершины
           }
           t[s]=0; // длинейший путь путь из s в s равен 0
           x[s]=1; // Для вершины s найден длинейший путь
           int v=s;    // Делаем s текущей вершиной
           while(1){
      // Перебираем все вершины, смежные v, и ищем для них длинейший путь
      for(int u=0; u<n;u++){
         if(A->graf[v][u]==0){
             continue; // Вершины u и v несмежные, переходим к следующей
         }
         if((x[u]==0) && (t[u] < t[v] + 1)){ //Если для вершины u еще не найден длинейший путь и новый путь в u длинее чем старый, то
                     t[u]=t[v]+1;  //запоминаем большую длину пути в массив t и
         }
      }
      // Ищем из всех длин некратчайших путей самый короткий
      int w=0;  // Для поиска самого самого длинного пути
      v=-1;            // В конце поиска v - вершина, в которую будет найден новый длинейший путь путь. Она станет  текущей вершиной
      for(int u=0; u<n; u++){ // Перебираем все вершины.
         if(x[u]==0 && t[u]>w){ // Если для вершины не найден длинейший путь и если длина пути в вершину u больше уже найденной, то
            v=u; // текущей вершиной становится u-я вершина
            w=t[u];
         }
      }
      if(v==-1){
          break;  //нужного пути не существует
      }
      if(v==g){ // Найден кратчайший путь,        
       if (t[g] > max){
           max=t[g];
       }
       break;
      }
      x[v]=1;
   }
}
   }
   return(max);
}
Это написано для графов, я не знаю, может поможет чем-то
Cee K
1 / 1 / 0
Регистрация: 05.04.2012
Сообщений: 46
11.07.2012, 17:47  [ТС]     Алгоритм Дейкстры для лабиринта #3
Lel'ka, еще бы описание этой структуры посмотреть
Lel'ka
8 / 8 / 2
Регистрация: 10.07.2012
Сообщений: 38
11.07.2012, 19:05     Алгоритм Дейкстры для лабиринта #4
C
1
2
3
4
const int max_size=8;
struct graph{
 int graf[max_size][max_size];
};
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
12.07.2012, 18:45     Алгоритм Дейкстры для лабиринта #5
Нужно модифицировать не алгоритм Дейкстры, а входные данные.
У нас есть N = n(высота) * m(ширина) клеток - поле лабиринта.
Построим матрицу смежности N * N, где matrix[i, j] = 1, если есть путь из вершины i в вершину j(т.е. если эти клетки находятся вплотную друг к другу, и обе клетки не являются стеной), иначе matrix[i, j] = 0.
Либо можно построить списки смежности по аналогии.
Ну а потом просто прогнать классический алгоритм Дейкстры.
Кстати, здесь принципиально Дейкстру использовать? bfs здесь будет более уместен, ибо он проще и быстрее.
Yandex
Объявления
12.07.2012, 18:45     Алгоритм Дейкстры для лабиринта
Ответ Создать тему
Опции темы

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