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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.92
Cee K
1 / 1 / 0
Регистрация: 05.04.2012
Сообщений: 46
#1

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

11.07.2012, 17:27. Просмотров 1796. Ответов 4
Метки нет (Все метки)

Лабиринт задается матрицей, где 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++
Трехмерный лабиринт выглядит следующим образом На примере 3*3*3 Числа 0,1,2... секторы лабиринта -1 проходимые участки -2 стенки ...

Наименьшее количество ходов для прохождения игры, алгоритм Дейкстры - C++
Есть игра. Она собой представляет прямую линию. Цель игры достаться от начала в точке с координатой 0, к финишу. По пути могут встречаться...

Алгоритм Дейкстры для матрицы смежности А размером NxN, нарисовать блок-схему по коду - C++
Здравствуйте! Помогите, пожалуйста, сделать блок -схему по готовому коду: #include "stdafx.h" #include <iostream> #include <conio.h>...

Алгоритм обхода лабиринта - C++
Помогите реализовать алгоритм обхода лабиринта, на примере матрицы nxn, где 1 (единицы) это проходимые элементы, а 0 (нули) это...

Простенький алгоритм выхода из лабиринта - 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
1929 / 1195 / 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 здесь будет более уместен, ибо он проще и быстрее.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.07.2012, 18:45
Привет! Вот еще темы с ответами:

Алгоритм Дейкстры - C++
День добрый! Есть игровое поле M*M. Количесво графов - N. Есть матрица смежности этого игрового поля. Получить элемент матрицы можно...

Алгоритм Дейкстры - C++
Что-то у меня Дейкстра не работает... прошу помощи у вас... Сам уже часа 1.5 сижу и не могу найти ошибку...#include &lt;iostream&gt; #include...

Алгоритм Дейкстры С++ - C++
Реализовать алгоритм поиска кратчайшего пути. Алгоритм Дейкстры. Представление графа – матрица смежности. как можно после того как...

Алгоритм Дейкстры - C++
Помогите найти ошибку плз. Первый шаг алгоритма выполняет правильно,а дальше-нет. #include&lt;iostream&gt; #include&lt;fstream&gt; ...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
12.07.2012, 18:45
Ответ Создать тему
Опции темы

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