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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Составить описание класса, обеспечивающего представление матрицы произвольного размера http://www.cyberforum.ru/cpp-beginners/thread622419.html
Составить описание класса, обеспечивающего представление матрицы произвольного размера с возможностью изменения числа строк и столбцов, вывода на экран подматрицы любого размера и всей матрицы. вот код: описание класса есть, только нужно дописать int main! напишите пожалуйста вроде бы это совсем не сложно, но так я с программированием не связан то сам не могу( #include<iostream> using...
C++ Бешенный плай bool LoadPly (char *FileName , TModel &Model , float Unit ) { std::string Buffer; std::string Buffer1; std::ifstream File; bool VertexFlag; bool ... http://www.cyberforum.ru/cpp-beginners/thread622395.html
Удаление вершины бинарного дерева C++
Как удалять вершины бинарного дерева вместе с потомками?
C++ Ошибки в программе
Мне необходимо реализовать алгоритм сортировки каскадным слиянием со специальным распределением. Я написал программу: #include <stdio.h> #include <conio.h> int main() { int a={12,4,0,47,-32,200,14,7890,-1,33};
C++ iostream http://www.cyberforum.ru/cpp-beginners/thread622369.html
пишу в VS 2010 подключаю библиотеку: #include <iostream> в тебе программы подчеркивает cout, cin и endl в ошибках пишет идентификатор неопределен. помогите, в чем дело?
C++ Задача из книги Дейтел Как программировать на C++ Друзья! Я начал не так давно заниматься программированием. Имелся опыт с паскалем,но решил изучать С++. Начал изучение по книге Дейтелов. Дошел до 5 главы,и тут начались затруднее с решением задач. Задача 5.19 Рассчитайте значение pi как сумму бесконечного ряда подробнее

Показать сообщение отдельно
Lel'ka
8 / 8 / 2
Регистрация: 10.07.2012
Сообщений: 38
11.07.2012, 17:37     Алгоритм Дейкстры для лабиринта
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);
}
Это написано для графов, я не знаю, может поможет чем-то
 
Текущее время: 00:01. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru