VPF::находнение всех путей в графе - Форум программистов

xber9

Дата 31.10.2012, 13:44 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 245
Регистрация: 21.1.2007

Репутация: нет
Всего: нет

народ привет
не знаю насколько вопрос подходит теме (если что перенесет)
и так есть граф описывающий метрополитен Москвы
и функция которая ищет минимальный путь от а до б

Код


    <?php 
    // определяем граф
    $graph = array(
    //зеленая ветка
    //рречной  - водный стадион 
      55  => array(60),
    //  водныфй -(речной, войковская) 
      60  => array(55,74),
    //войковская =(водныйб сокол)
      74  => array(60,75),
    //сокол-( войковский аэропорт)
      75  => array(74,76),
      //  аэропоорт -(сокол динамо)
      76  => array(75,62),
// динамо - (аэропорт , белорусская)
      62  => array(76,63),
      //БЕЛОРУССКАЯ зеленая-( БЕЛОРУССКАЯ кольц, ДИНАМО, маяковская)
     63  => array(153,62,47),
//маяковского -(белоруская зеленая,  тверская)
    47  => array(63,48),
    // тверская-( маяковского, пушкинская, чеховская, театральная)
     48  => array(47,52,53, 152),
    // театральная-(тверская, охотный,пл революции,новокузнецувя )
     152  => array(48,44,24,34),
         //новокущнецкая-(театравльныя,  третьявка желтая и отрна, повелецкая зеленая,) 
          34  => array(152,33,164, 31),
      //повелецкая зеленая-(новокущнецкая, повелекая кольцвая, автозаводская)
          31  => array(34,32,18),
          //автозаводская-( повелецкая зеленая, коломеннская)
          18  => array(31,113),
          //коломеннская-(автозаводская, каширская зененая)
          113 => array(18,114),
//каширская зененая -(коломеннская, кашрская голубая, кантимировкская) 
          114 => array(113,154, 147),
          //кантимировкская-(каширская зененая, царицкно)
          147 => array(114,150),
          //ЦРИЦКНО -(кантимировкска,  орехово)
          150 => array(147,148),
          //орехово-( царицено домодедовская)
          148 => array(150,151),
          //домодедовская-*(орехово, красногвыардейская)
          151 => array(148,149),
          //красногвыардейская-домодедовская
          149 => array(151),
          
    //серая ветка      
    //алтуфьево -( биберево)
          59 => array(58),
          //биберево -(алтуфьево, отрадное)
          58 => array(59,57),
    //отрадное -(биберево, владыкино)
              57 => array(58,73),
              //владыкино-(отрадное, петровско-разумовское) 
              73 => array(57,69),
              //петровско-разумовское-( владыкино, темарязевскач)
              69 => array(73,71),
              //темерязв -(петровско-разумовское, дмировская)
              71 => array(69,70),
//дмтровская -(темерзычув, савеловская
    70 => array(71,72),
    //савеловская-(дмитровка, менделева)
    72 => array(70,10),
 // менделевская-(савеловская,новослободская, цветной бульвар)
    10 => array(72,7,54),
    ///цветной бульвар -( меднелевскаЯ, чеховсекая)
    54 => array(10,53),
    //чеховская -(цветной, тверская,пушкниская, борровитсякая)  
    53 => array(54,48,52, 42),
    
     
     //кольцквая
      //БЕЛОРУССКАЯ кольц-(БЕЛОРУССКАЯ зеленая  новослободская, краснопреснч)
     153  => array(63,7, 61),
     //новослоболская -( мендеевская, БЕЛОРУССКАЯ кольц, проспект мира кольц )
     7  => array(10,153, 6),
     
     //повелекая кольцвая-(повелекая зеленая, таганка кольцевая, добрыненская
     32=>array(31,30, 17),


     // глубая ветка
//кашрская голубая-(кашрская зеленая, варшавская(
    154=>array(114,92)
      // ................................................
    );

   
   
    function find_path($graph, $start, $end, $path)
    {
      $path[] = $start;
      
      if ($start == $end)
         return $path;
      
      if (!isset($graph[$start]))
         return false;
      
      $shortest = array();

      foreach($graph[$start] as $node) {
   if (!in_array($node, $path)) {
     $newpath = find_path($graph, $node, $end, $path);
     if ($newpath) {
       if (!$shortest || (count($newpath) < count($shortest)))
         $shortest = $newpath;
     }   
   }
      }
      return $shortest;
    }
    if (isset($_GET['from']) && isset($_GET['to'])) 
    {
      if (in_array($_GET['from'], array_keys($graph)) &&  in_array($_GET['to'], array_keys($graph))) 
      {
    
     $shortestPath = find_path($graph, $_GET['from'], $_GET['to'],null);

$out='{"routes":{"from":"'.$_GET['from'].'","to":"'.$_GET['to'].'","time":16,"transfers":1,"waypoints":[';

//     echo($out);
     foreach($shortestPath as $station) {

$out.='"'.$station.'",';
     }
$out=substr($out, 0, strlen($out)-1);     
     $out.=']}}';
     echo($out);
      } else { 
   echo(' 400');
       }
      } ?>

я понимаю что эта функция  ищет  минимальное расстояние в зависимости от количества пройденных точек
но мне нужно  чтобы она искала  ни минимальный путь,  а  путь с минимумом  пересадок с ветки на ветку
я вижу это так, что сначала мне надо  получить все возможные пути из А в Б  а потом их проверять на наличие пересадок

как проверять я себе тоже представляю (сделать массив с пересадками и проверять соответствия )
но как заставить мою функцию вернуть все  возможные пути я не знаю

помогите изменить функцию чтобы она возвращала все возможные пути от А  в Б
заранее спасибо smile

skyboy

Дата 31.10.2012, 18:15 (ссылка)

(нет голосов)

Загрузка ...

неОпытный

Профиль
Группа: Модератор
Сообщений: 9820
Регистрация: 18.5.2006
Где: Днепропетровск

Репутация: 1
Всего: 260

если опишешь, как в настоящий момент находишь минимальный путь(название алгоритма, или словесное описание), перенесу в раздел "Алгоритмы"

xber9

Дата 1.11.2012, 12:53 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 245
Регистрация: 21.1.2007

Репутация: нет
Всего: нет

Алгоритмы можно вкратце описать так: для вершины, которую мы еще не посетили, нужно отыскать все еще не посещенные смежные вершины и повторить поиск для них
то есть поиск в глубину

skyboy

Дата 1.11.2012, 15:49 (ссылка)

(нет голосов)

Загрузка ...

неОпытный

Профиль
Группа: Модератор
Сообщений: 9820
Регистрация: 18.5.2006
Где: Днепропетровск

Репутация: 1
Всего: 260

тебе надо кастомизировать алгоритм добавлением весов.
то есть, вместо

Цитата

count($newpath) < count($shortest)

использовать

Код


path_length($newpath) < path_length($shortest)

а path_length для станции на той же ветке добавляет +1, а для станции другой ветки(пересадка) — скажем, +3.

xber9

Дата 1.11.2012, 17:51 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 245
Регистрация: 21.1.2007

Репутация: нет
Всего: нет

Цитата(skyboy @ 1.11.2012, 15:49

)

а path_length для станции на той же ветке добавляет +1, а для станции другой ветки(пересадка) — скажем, +3.

бррр что то не соображу как будет path_length выглядить и как записывать данные о весе
для меня это все в новинку так что сори что сразу не впиливаю)

baldina

Дата 1.11.2012, 18:06 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

Репутация: 1
Всего: 101

Цитата(xber9 @ 1.11.2012, 12:53

)

то есть поиск в глубину

поищи в ширину. погляди алгоритм Дейкстры

xber9

Дата 1.11.2012, 19:08 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 245
Регистрация: 21.1.2007

Репутация: нет
Всего: нет

Цитата(baldina @ 1.11.2012, 18:06

)

поищи в ширину. погляди алгоритм Дейкстры

искал но е понял как можно реализовать чтобы использовать такую запись данных как уменя ибо данные уже готовы

а как все это интерпритировать в матрицу смежности не знаю

skyboy

Дата 1.11.2012, 20:58 (ссылка)

(нет голосов)

Загрузка ...

неОпытный

Профиль
Группа: Модератор
Сообщений: 9820
Регистрация: 18.5.2006
Где: Днепропетровск

Репутация: 1
Всего: 260

Цитата(xber9 @ 1.11.2012, 16:51

)

бррр что то не соображу как будет path_length выглядить и как записывать данные о весе

во-первых, тебе нужно решить, какой вес будет у пересадки. то есть, начиная с какого количества "проехать лишние N станция без пересадок" предпочтительнее, чем совершить одну пересадку и не ехать эти самые N станций.
во-вторых, count($newpath) — это простейший алгоритм рассчета "длины пути" — каждая станция считается за единицу. чем больше станций — тем больше сумма — тем больше длина. я ж предлагаю вместо count использовать самописную функцию, которая для заданного списка станций будет увеличивать значение длины пути на 1 для каждой станции, кроме пересадочных. А для станций пересадки — увеличивать сразу на N.

xber9

Дата 1.11.2012, 21:17 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 245
Регистрация: 21.1.2007

Репутация: нет
Всего: нет

Цитата(skyboy @ 1.11.2012, 20:58

)

во-вторых, count($newpath) — это простейший алгоритм рассчета "длины пути" — каждая станция считается за единицу. чем больше станций — тем больше сумма — тем больше длина. я ж предлагаю вместо count использовать самописную функцию, которая для заданного списка станций будет увеличивать значение длины пути на 1 для каждой станции, кроме пересадочных. А для станций пересадки — увеличивать сразу на N.

то есть мне надо сделать массив в котором будут все id станций с которых можно сделать пересадку
"самописная" функция принимает в себя массив точек и для каждой из них проверяет принадлежит ли она массиву пересадок
если принадлежит то возвращаемое значение увеличивается на какое то большое число
если нет то увеличивается на 1

я правельно понимаю или что то не так

baldina

Дата 1.11.2012, 22:52 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

Репутация: 1
Всего: 101

Цитата(xber9 @ 1.11.2012, 19:08

)

но е понял как можно реализовать чтобы использовать такую запись данных как уменя

у тебя списки смежности. все реализуемо.

Добавлено через 1 минуту и 18 секунд

Цитата(xber9 @ 1.11.2012, 19:08

)

ибо данные уже готовы

если задача требует, можно и по-другому приготовить, не правда ли?
хотя в данном случае и так пойдет

Добавлено через 5 минут и 23 секунды

Цитата(baldina @ 1.11.2012, 22:52

)

у тебя списки смежности

поглядел, вижу что не прав. но все равно реализуемо.
требуемая для dfs и bfs информационная операция на графе всего лишь одна - для данного узла получить список узлов, в которые ведут исходящие ребра.

xber9

Дата 1.11.2012, 23:33 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 245
Регистрация: 21.1.2007

Репутация: нет
Всего: нет

Цитата(baldina @ 1.11.2012, 22:52

)

поглядел, вижу что не прав. но все равно реализуемо.

переделывать в матрицу не времени так что придктся юзать глубину

baldina

Дата 2.11.2012, 08:59 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

Репутация: 1
Всего: 101

Цитата(xber9 @ 1.11.2012, 23:33

)

переделывать в матрицу не времени так что придктся юзать глубину

изучать калькулятор времени нет, поэтому будем считать в столбик.

xber9, не решишь эту задачу поиском в глубину.
поглядел еще раз, опять вижу списки смежности. вчера мозг устал. так вот, переделывать в матрицу необходимости нет.

xber9

Дата 2.11.2012, 13:04 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 245
Регистрация: 21.1.2007

Репутация: нет
Всего: нет

Цитата(baldina @ 2.11.2012, 08:59

)

поглядел еще раз, опять вижу списки смежности. вчера мозг устал. так вот, переделывать в матрицу необходимости нет.

смотрел вчера на вики реализацию на псевдокоде
но моих мозгов не хватает чтобы понять как это померкнуть на php и использовать свои списки (нашел 1 реализацию на javasctript которую можно на php перекинуть но там матрица
так что я в тупике
увы

Это сообщение отредактировал(а) xber9 - 2.11.2012, 14:35

xber9

Дата 2.11.2012, 15:44 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 245
Регистрация: 21.1.2007

Репутация: нет
Всего: нет

вот та самая функция переведенная на пхп
а как ее для моих данных адаптировать?

Код


    

//---------------------------------------------------------------------------
//Алгоритм Дейкстры.поиска кратчайшего пути
function fin($s, $g){
$v;

  $VERTEXES =6;

   $infinity=1000;                     // Бесконечность

   $p= $VERTEXES;             // Количество вершин в графе
   $a=array(                   array(0,1,0,0,1,3),  
                               array(1,0,5,0,0,1),
                               array(0,5,0,5,20,1),
                               array(0,0,5,0,3,2),
                               array(1,0,20,3,0,10),
                               array(3,1,1,2,10,0)
                                );
 
   // Будем искать путь из вершины s в вершину g
   // s;                   // Номер исходной вершины
   // g;                   // Номер конечной вершины
   $x=array(); //Массив, содержащий единицы и нули для каждой вершины,
                  // x[i]=0 - еще не найден кратчайший путь в i-ю вершину,
                  // x[i]=1 - кратчайший путь в i-ю вершину уже найден
   $t= array();  //t[i] - длина кратчайшего пути от вершины s в i
   $h=array();  //h[i] - вершина, предшествующая i-й вершине
                 // на кратчайшем пути
 
   // Инициализируем начальные значения массивов
   $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
         }
      }
 
      // Ищем из всех длин некратчайших путей самый короткий
      $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)
      {
        echo( "Нет пути из вершины ".$s." в вершину ".$g.".");
         break;
      }
      if($v==$g) // Найден кратчайший путь,
      {        // выводим его
         echo("Кратчайший путь из вершины ".$s." в вершину ".$g.":");
       $u=$g;
       while($u!=$s)
         {
            echo(" ".$u);
            $u=$h[$u];
         }
         echo(" ".$s.". Длина пути - ".$t[$g]);
       break;
      }
      $x[$v]=1;
   }
}
/*Программа запрашивает вершины s и q и выводит кратчайший путь. Например, после ввода s = 3, q = 6, программа выводит 
 
Нет пути из вершины 3 в вершину 6. 
 
После ввода s = 0, q = 2 программа выводит 
 
Кратчайший путь из вершины 0 в вершину 2: 2 5 1 0. Длина пути = 3.*/
 
//---------------------------------------------------------------------------

Это сообщение отредактировал(а) xber9 - 2.11.2012, 15:47

Aliance

Дата 2.11.2012, 18:04 (ссылка)

(нет голосов)

Загрузка ...

I ♥ <script>

Профиль
Группа: Модератор
Сообщений: 6418
Регистрация: 2.8.2004
Где: spb

Репутация: нет
Всего: 137

называть переменные $v, $w, $u и т.п. - мощно.

--------------------

• Все о событиях
• Объекты и массивы
• ОКНА И ФРЕЙМЫ

JAVA ≠ JavaScript

xber9

Дата 2.11.2012, 18:39 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 245
Регистрация: 21.1.2007

Репутация: нет
Всего: нет

увы но как я и говорил код не мой

baldina

Дата 2.11.2012, 18:58 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

Репутация: 1
Всего: 101

обобщенный поиск в ширину

Код


function bfs ($graph, $node, $current) {
 $queue[] = array(null,$node);
 $marks[$node] = true;
 while (count($queue) > 0) {
   list($v,$u) = array_shift ($queue);
   if (is_callable ($current))
     $current ($v,$u);
   foreach (get_adjacent ($graph, $u) as $w)
     if (!$marks[$w]) {
       $marks[$w] = true;
       $queue[] = array($u,$w);
     }
 }
}

эта функция не зависит от представления графа, для адаптации к конкретному представлению служит функция get_adjacent ();
реализация bfs не самая общая, но достаточная для наших целей: для каждой посещенной вершины вызывается пользовательская функция-посетитель $current(), куда передается ребро (текущая вершина и та, из которой мы сюда пришли).

реализация функции-посетителя для алгоритма поиска кратчайщих путей по Дейкстре:

Код


function dijkstra_visitor ($v, $u) {
  global $cost, $path;
  if (!isset($cost[$u]) || $cost[$u] > $cost[$v]+1) {
    $cost[$u] = $cost[$v]+1;
    if ($v)
      $path[$u] = $path[$v];
    $path[$u][] = $u;
  }
}

она почти тривиальна, в качестве веса любого ребра используется единица (в вашем графе веса не указаны, поэтому я не стал усложнять).
в глобальных массивах $cost и $path хранятся стоимости(длины) путей и сами пути соответственно

что бы применить это к вашей структуре нужен адаптер. в данном случае он тривиален:

Код


function get_adjacent ($graph, $v) {
  return isset($graph[$v]) ? $graph[$v] : array();
}

ну вот и все, остальное самостоятельно допилите
http://codepad.org/d2eGCrci

baldina

Дата 2.11.2012, 20:04 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

Репутация: 1
Всего: 101

Цитата(xber9 @ 31.10.2012, 13:44

)

я вижу это так, что сначала мне надо получить все возможные пути из А в Б а потом их проверять на наличие пересадок

для минимизации пересадок измените вес для пересадки (уже говорили про это)

Цитата(baldina @ 2.11.2012, 18:58

)

$cost[$u] > $cost[$v]+1

кстати, вам нужно минимум пересадок или минимальное время?

xber9

Дата 2.11.2012, 20:05 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 245
Регистрация: 21.1.2007

Репутация: нет
Всего: нет

огромное спаисбо зхавтар буду разбираться
если что надеюсь поможете но думаю все норм еще рас спс

Добавлено @ 20:08

Цитата(baldina @ 2.11.2012, 20:04

)

кстати, вам нужно минимум пересадок или минимальное время?

вообще то и то  и то в зависимости  от выбора пользователя
кстати как правельно задать  веса для пересадок?
как отдельный массив ? и проверять принадлежит ли дуга VU этому массиву и если да то  делатть не +1 а +много или как?

Это сообщение отредактировал(а) xber9 - 2.11.2012, 23:54

baldina

Дата 3.11.2012, 13:32 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

Репутация: 1
Всего: 101

Цитата(xber9 @ 2.11.2012, 20:05

)

как правельно задать веса для пересадок?

по разному можно. например, опциональным параметром (т.е. элемент массива смежности может быть массивом (станция, вес)
более правильно, думаю, задавать веса для всех ребер (значения времени в минутах, например), включая время пересадок.

но если вводить вес, программу придется немного переделать: мой dijkstra_visitor() по сути relax_visitor(), они совпадают для невзвешенного графа, а для взвешенного графа dfs bfs с обычной очередью недостаточно, нужно иметь очередь с приоритетами.

Добавлено @ 13:39

Цитата(xber9 @ 2.11.2012, 20:05

)

проверять принадлежит ли дуга VU этому массиву и если да то делатть не +1 а +много

можно и так, можно добавить явные пути для пересадок, можно, как я выше написал. зависит от желаемого результата и возможных расширений в будущем. если приоритет пересадки делать заведомо большим, чем время обычного проезда до следующей станции, пересадки будут выбираться, только если нет другого пути.
для себя, например, я определил, что среднее время между станциями и среднее время одной пересадки - 2.5мин. это, конечно, не дает наименьшее число пересадок, но время предсказывает хорошо и дает быстрые пути. для бабушки, кторая не может бегать между станциями, пересадка может стоить и 10мин.

Это сообщение отредактировал(а) baldina - 3.11.2012, 14:27

xber9

Дата 3.11.2012, 13:41 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 245
Регистрация: 21.1.2007

Репутация: нет
Всего: нет

Цитата(baldina @ 3.11.2012, 13:32

)

но если вводить вес, программу придется немного переделать: мой dijkstra_visitor() по сути relax_visitor(), они совпадают для невзвешенного графа, а для взвешенного графа dfs с обычной очередью недостаточно, нужно иметь очередь с приоритетами.

извиняюсь но я практически ничего не понял  из этой фразы
где об этом можно почитать или может если для вас это не слишком затруднительно покажете как изменить ваш  пример ( конечно если не об очень многом прошу)
еще рас прошу прощения если очень сильно напрягаю и туплю   smile

Добавлено @ 13:48

Цитата(baldina @ 3.11.2012, 13:32

)

более правильно, думаю, задавать веса для всех ребер (значения времени в минутах, например), включая время пересадок.

идея со временем кажется самое то тк время пути тоже надо будет подсчитывать

я так понимаю вы предлагаете изменить исходные данные типа так

Код


$graph = array(
      55  => array(60=> array(3)),
      60  => array(55=> array(3),74=> array(4)),
      74  => array(60=> array(3),75=> array(6)),
...........

но тогда как менять фунцию ибо я как всегда не понимаю (не хватает математических знаний как я пологаю)

Это сообщение отредактировал(а) xber9 - 3.11.2012, 13:50

baldina

Дата 3.11.2012, 14:43 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

Репутация: 1
Всего: 101

да, фраза не очень понятная))) и с ошибкой: не dfs, а bfs - поиск в ширину
в поиске в ширину в очередь заносятся смежные вершины, потом из очереди вынимаются и обрабатываются. если весов нет, длина пути соответствует числу проходимых вершин
если веса есть, нужно из очереди выбирать вершину с наименьшим весом(приоритетом), поэтому требуется очередь с приоритетами (это и будет алгоритм дейкстры).
в любом алгоритме поиска кратчайших путей (в т.ч. в простейшем на основе поиска в ширину) используется т.н. функция relax для релаксирования путей, т.е. поддержания списка кратчайших путей и их весов.
для очередей с приоритетами в php можно использовать класс SplMinHeap

Цитата(xber9 @ 3.11.2012, 13:41

)

где об этом можно почитать

любая книга по алгоритмам,
http://en.wikipedia.org/wiki/Breadth-first_search
http://ru.wikipedia.org/wiki/%D0%90%D0%BB%...%82%D1%80%D1%8B

Цитата(xber9 @ 3.11.2012, 13:41

)

55 => array(60=> array(3)),

да, что-то типа этого.

Добавлено через 1 минуту и 9 секунд
будет время, попробую написать, но позже...

xber9

Дата 3.11.2012, 15:52 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 245
Регистрация: 21.1.2007

Репутация: нет
Всего: нет

Цитата(baldina @ 3.11.2012, 14:43

)

будет время, попробую написать, но позже...

если будет возможность напишите плиз ибо сам я не уверен что до конца разберусь

baldina

Дата 4.11.2012, 12:24 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

Репутация: 1
Всего: 101

вот http://codepad.org/OoaxvDF9
это многословнее, чем раньше, но подходит для адаптации к разным представлениям графа и алгоритмам

Добавлено через 8 минут и 34 секунды
кстати, простейшая модификация первой реализации для работы с весами - просто перенести вызов $current:

Код


function bfs ($graph, $node, $current) {
 $queue[] = array(null,$node);
 $marks[$node] = true;
 while (count($queue) > 0) {
   list($v,$u) = array_shift ($queue);
   // $current ($v,$u);
   foreach (get_adjacent ($graph, $u) as $w)
     $current ($u,$w);
     if (!$marks[$w]) {
       $marks[$w] = true;
       $queue[] = array($u,$w);
     }
 }
}

Это будет некая разновидность алгоритма Беллмана-Форда. Для графов без отрицательных весов этот алгоритм менее эффективен, чем Дейкстры, но для пары сотен вершин и ребер думаю разница несущественная.

xber9

Дата 4.11.2012, 16:54 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 245
Регистрация: 21.1.2007

Репутация: нет
Всего: нет

Цитата(baldina @ 4.11.2012, 12:24

)

вот http://codepad.org/OoaxvDF9
это многословнее, чем раньше, но подходит для адаптации к разным представлениям графа и алгоритмам

большое спасибо очень выручил- буду постепенно разбираться
я правельно понимаю что для того чтобы считался путь с минимумом пересадок достаточно значительно увеличить вес пересадки а чтобы искал просто кратчайший путь то надо обратно уменьшить вес

и еще вопрос ( так как еще не разобрался) как вывести на печать общий вес пути from - to

baldina

Дата 4.11.2012, 17:35 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

Репутация: 1
Всего: 101

Цитата(xber9 @ 4.11.2012, 16:54

)

я правельно понимаю что для того чтобы считался путь с минимумом пересадок достаточно значительно увеличить вес пересадки а чтобы искал просто кратчайший путь то надо обратно уменьшить вес

да.
кстати, минимум пересадок может давать очень плохие пути. например, динамо-савеловская через тверскую. даже бабушка так не поедет.

Цитата(xber9 @ 4.11.2012, 16:54

)

вывести на печать общий вес пути from - to

содержится в

Код


$this->cost[$to];

xber9

Дата 4.11.2012, 18:03 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 245
Регистрация: 21.1.2007

Репутация: нет
Всего: нет

Цитата(baldina @ 4.11.2012, 17:35

)

я понимаю поэтому буду давать пользователю выбор как ему посчитать
мин времени или мин пеерсадок
>динамо-савеловская через тверскую
я поеду так как инвалиду легче дальше проезхать чем ходить по переходам)
еще рас спасибо

xber9

Дата 4.11.2012, 23:05 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 245
Регистрация: 21.1.2007

Репутация: нет
Всего: нет

НЕ охото начинать новую тему поэтому спрошу тут
переделал данные вот так

Код


$t0=1;
$t1=2;
$t2=3;
$t3=4;
$t4=5;
    
    // определяем граф
    $graph = array(
    63  => array(153=>$t2,62=>3,47=>2),
     48  => array(47=>2,52=>$t1,53=>$t2, 152=>2),
);

где t1....t4 времена ( веса) для пересадок
далее при определнных условиях я делаю так

Код



if(<пользователь выбирает мин пересадок>){

$t0=100;
$t1=100;
$t2=100;
$t3=100;
$t4=100;

<расчет пути>

}

однако данные внутри описания графа ($graph) отсались прежними а не =100

вопрос как переинициализоваровать граф чтобы туда записались сотни ( надеюсь понятно обьяснил)

Это сообщение отредактировал(а) xber9 - 4.11.2012, 23:22

xber9

Дата 4.11.2012, 23:20 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 245
Регистрация: 21.1.2007

Репутация: нет
Всего: нет

или как по другому изменять веса для пересадок при определенных условиях

baldina

Дата 5.11.2012, 00:47 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

Репутация: 1
Всего: 101

ситуация аналогична такой:

Код


$a=1;
$b=$a;

if (...) {
  $a = 2;
  // и тут мы с удивлением обнаруживаем что $b не изменилось)))
}

варианты решения:

Код


$b=1;
if (...) {
  $b = 2;
}

Код


$a=1;
$b=&$a; // по ссылке

if (...) {
  $a = 2;
  // и тут мы с радостью обнаруживаем что $b изменилось)))
}

а самый простой и правильный вариант вероятно такой:

Код


$a=1;
if (...) {
  $a = 2;
}
$b=$a;

xber9

Дата 5.11.2012, 10:49 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 245
Регистрация: 21.1.2007

Репутация: нет
Всего: нет

в моем случае удобней по ссылке
спсибо

xber9

Дата 6.11.2012, 21:41 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 245
Регистрация: 21.1.2007

Репутация: нет
Всего: нет

tobaldina
привет сново проблема
загрузил  твой код на хостинг от агвы и выяснилось что он не  работает
хотя у меня дома на денвере все норм
на агаве при вызове скрипта  ругается так

Parse error: parse error, unexpected T_STRING, expecting T_OLD_FUNCTION or T_FUNCTION or T_VAR or '}' in /home/interes1/public_html/metro/ROTES.php on line 9

9ая строка это    private $marks = array();

помоги плиз

Добавлено через 14 минут и 44 секунды
на хосте php 4

xber9

Дата 6.11.2012, 22:06 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 245
Регистрация: 21.1.2007

Репутация: нет
Всего: нет

вопрос уже не срочный так как нашел где в агаве перекючить на php5
но если будет время напиши )

baldina

Дата 6.11.2012, 22:24 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

Репутация: 1
Всего: 101

я уже не помню, что было в php4, старье ведь. на php.net написано

Цитата

Начиная с версии PHP 5 объектная модель была полностью переписана, она стала более производительной и функциональной. Это было главным изменением с версии PHP 4. В PHP 5 теперь полная объектная модель.

так что неудивительно...
последняя версия php - 5.4, там много интересных вещей, а поскольку я писал на codepad, использовались средства не выше 5.2.5
и spl на codepad нет, поэтому класс очереди на основе SplHeap закомментирован

Добавлено через 1 минуту и 40 секунд

Цитата(xber9 @ 6.11.2012, 21:41

)

9ая строка это private $marks = array();

видимо private не понравилось

xber9

Дата 13.11.2012, 22:36 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 245
Регистрация: 21.1.2007

Репутация: нет
Всего: нет

to baldina

Привет  сново я со своим метро и с проблемами)

на основе твоего кода(поменял только формат вывода) сделал схему метро ( еще не все ветка описаны но все же)  вот тут
в результате выяснилось что не всегда выдает самый короткий ( по времени=весу) маршрут (тоесть посылает  через ж...)
конкретный пример
начальная точка - театральная ( темно зеленая ветка), конечная -красные ворота (красная ветка), в данном случае функция  посылает через третьяковку вместо Охотного ряда
хотя если начальную и конечную  точки поменять местами то   посылает нормально

то же самое если
начальная =боровицкая ( серая ветка)  конечная = красные ворота  ( или любая станция за ними вверх)

я не могу понять в чем проблемап
очень прошу помогите
ЗЫ при клике по станции на сайте  вылезает окошко с id станции в графе

вот описание графа

Код


<?php
$t0=1;
$t1=2;
$t2=3;
$t3=4;
$t4=5;
    
    // определяем граф
    $graph = array(
    //зеленая ветка
    //рречной  - водный стадион 
      55  => array(60=>2),
    //  водныфй -(речной, войковская) 
      60  => array(55=>2,74=>3),
    //войковская =(водныйб сокол)
      74  => array(60=>3,75=>3),
    //сокол-( войковский аэропорт)
      75  => array(74=>3,76=>2),
      //  аэропоорт -(сокол динамо)
      76  => array(75=>2,62=>3),
// динамо - (аэропорт , белорусская)
      62  => array(76=>3,63=>3),
      //БЕЛОРУССКАЯ зеленая-(  ДИНАМО, БЕЛОРУССКАЯ кольц, маяковская)
     63  => array(62=>3, 153=>&$t2,47=>2),
//маяковского -(белоруская зеленая,  тверская)
    47  => array(63=>2,48=>2),
    // тверская-( маяковского, пушкинская, чеховская, театральная)
     48  => array(47=>2,52=>&$t1,53=>&$t2, 152=>2),
    // театральная-(тверская, охотный,пл революции,новокузнецувя )
     152  => array(48=>2,44=>&$t3,24=>&$t2,34=>3),
         //новокущнецкая-(театравльныя,  третьявка желтая и отрна, повелецкая зеленая,) 
          34  => array(152=>3,33=>&$t1,164=>&$t1, 31=>2),
      //повелецкая зеленая-(новокущнецкая, повелекая кольцвая, автозаводская)
          31  => array(34=>2,32=>&$t2,18=>3),
          //автозаводская-( повелецкая зеленая, коломеннская)
          18  => array(31=>3,113=>5),
          //коломеннская-(автозаводская, каширская зененая)
          113 => array(18=>5,114=>4),
//каширская зененая -(коломеннская, кашрская голубая, кантимировкская) 
          114 => array(113=>4,154=>&$t0, 147=>3),
          //кантимировкская-(каширская зененая, царицкно)
          147 => array(114=>3,150=>2),
          //ЦРИЦКНО -(кантимировкска,  орехово)
          150 => array(147=>2,148=>3),
          //орехово-( царицено домодедовская)
          148 => array(150=>3,151=>2),
          //домодедовская-*(орехово, красногвыардейская)
          151 => array(148=>2,149=>3),
          //красногвыардейская-домодедовская
          149 => array(151=>3),
          
    //серая ветка      
    //алтуфьево -( биберево)
          59 => array(58=>3),
          //биберево -(алтуфьево, отрадное)
          58 => array(59=>3,57=>3),
    //отрадное -(биберево, владыкино)
              57 => array(58=>3,73=>3),
              //владыкино-(отрадное, петровско-разумовское) 
              73 => array(57=>3,69=>3),
              //петровско-разумовское-( владыкино, темарязевскач)
              69 => array(73=>3,71=>3),
              //темерязв -(петровско-разумовское, дмировская)
              71 => array(69=>3,70=>2),
//дмтровская -(темерзычув, савеловская
    70 => array(71=>2,72=>3),
    //савеловская-(дмитровка, менделева)
    72 => array(70=>3,10=>2),
 // менделевская-(савеловская,новослободская, цветной бульвар)
    10 => array(72=>2,7=>&$t2,54=>2),
    ///цветной бульвар -( меднелевскаЯ, трубная, чеховсекая)
    54 => array(10=>2, 178=>&$t1,53=>2),
    //чеховская -(цветной, тверская,пушкниская, борровитсякая) 
    53 => array(54=>2,48=>&$t2,52=>&$t2, 42=>3),
    //борровитсякая-(чеховская, библиотека им ленина, арбаттикая темно синяя полянка)
    42 => array(53=>3,23=>&$t4,156=>&$t1,36=>2),
    //полянка-(борровитсякая, серпуховская)
    36 => array(42=>2,20=>2),
//серпуховская-(понякка, добраненска, тульская )
    20 => array(36=>2,17=>&$t2, 19=>3),
    //тульская -( серпуховская, нагатинская)
    19 => array(20=>3,115=>4),
//нагатинская-(туьская,  нагорная_
    115 => array(19=>4,97=>2),
    // нагорная -(нагатинская, михайловский пр
    97 => array(115=>2,99=>2),
    //михайловский -( нагорная севастопольская))
    99 => array(97=>2,98=>2),
//севастопольская -( михайловский, каховская, чертновская
    98 => array(99=>2,94=>&$t0, 112=>2),
// чертновская -9севастопольская, южная)
    112 => array(98=>2,110=>3),
// южная -(чертанвская, пражская)
    110 => array(112=>3,111=>2),
    //пражская -(южная,ягеля)
    111 => array(110=>2,181=>3),
//ягеля -(прадская, анино)
    181 => array(111=>3,182=>2),
//анино-(ягеоя, б Димтря д)
    182 => array(181=>2,183=>2),
//б Димтря д-( анино, ул строкачалская)
    183 => array(182=>2,186=>2),
    //ул строкачалская-(б Димтря д, скоблевская)
    186 => array(183=>2,187=>4),
    //скоблевская-(ул строкачалская- ушакова)
    187 => array(186=>4,188=>1),
    // ушакова-(скоблевская горчакова)(
    188 => array(187=>1,189=>2),
    // горчакова-(ушакова бунинская алея)
        189 => array(188=>2,190=>2),        
//бунинская алея-(горчакова)
        190 => array(189=>2),
        
        //СВЕТЛО зеленая ветка
        // марьена роща - достоевского
            195 => array(194=>3),
            //достоевскго -9 мрьена роща, ТРУбная_
            194 => array(195=>3, 178=>3),
        // трубная-( достоевского,ветной, сереневый)
            178 => array(194=>3, 54=>&$t1, 179=>3),
        // сереневый-( трубная ,ветной, чистые пруды, тургеньевская, чкаловская)
            179=> array(178=>3, 43=>&$t2,49=>&$t2, 14=>3),
        // чкаловская-( сереневый,курская кольц, курская син, римская)
            14 => array(179=>3, 13=>&$t3, 155=>&$t2,123=>3),
        //римская -чувлоская? ильичв, креснянская )
            123 => array(14=>3,122=>&$t1, 167=>3),
        //креснянская-(римская, пролектраская, ддууьровка, ) 
            167 => array(123=>3,28=>&$t2, 165=>2),
        // ддууьровка, -(креснянская, кожуховская ) 
            165 => array(167=>2,21=>2    ),
// кожуховская -(ддууьровка, печатники) 
            21 => array(165=>2,146=>4    ),
// печатники -(кожуховская ,вожская ) 
            146 => array(21=>4,142=>3    ),
// вожская -(печатники,люблино) 
            142 => array(146=>3,145=>3    ),
// люблино-(вожская ,брастиславская) 
            145 => array(142=>3,143=>3    ),
// брастиславская - (люблино,марьино ) 
            143 => array(145=>3,144=>2    ),
// марьино -(брастиславская ) 
            144 => array(143=>2),

//кирптичная ветка
// меедведкогго -(бабушкинаскя)
            119 => array(118=>3),
// бабушкинаскя- (меедведкогго, свиблово )
            118 => array(119=>3, 121=>2),
// свиблово -(бабушкинаскя,ботанический  )
            121 => array(118=>2, 120=>2),
// ботанический -(свиблово вднх, )
            120 => array(121=>2, 68=>3),
// вднх-(ботанический, алексанлдровсквая, )
            68 => array(120=>3, 67=>2),
// алексанлдровсквая- (вднх рижская ,  )
            67 => array(68=>2, 9=>3),
// рижская  -(алексанлдровсквая, проспект имра)
        9 => array(67=>3, 8=>2),
// проспект имра -(рижская  ,проспект имра колтьц, сухаревская )
            8 => array(9=>2, 6=>&$t2, 50=>2),
// сухаревская -(проспект имра, тургеньевский   )
            50 => array(8=>2, 49=>2),
// тургеньевский -(сухаревская сереневый, чистые прудф  китай город)
            49 => array(50=>2, 179=>&$t2, 43=>&$t2, 26=>2),
// китай грод -(тургеньевская  ,китайгород фиол, третяковская )
            26 => array(49=>2, 163=>&$t0, 33=>3),
//  третяковская -( китай грод -треьяковская жеелтая октябрьская ,  )
            33 => array(26=>3, 164=>&$t0 ,34=>&$t1, 162=>3),
// октябрьская -(  третяковская , октябрьская кольц, шаьоловская)
            162 => array(33=>3, 35=>&$t2, 16=>3),
//  шаьоловская -(октябрьская  лененский пр )
            16 => array(162=>3,  96=>3),
// лененский пр -( шаьоловская академическая )
            96 => array(16=>3,  95=>3),
//  академическая -(лененский пр, профсаюзаня)
            95 => array(96=>3,  104=>2),
// профсаюзаня-( академическая, новык черемушки )
            104 => array(95=>2 ,  102=>2),
//  новык черемушки -( профсаюзаня, калужская )
            102 => array(104=>2,  106=>3),
// калужская-( новык черемушки,  беляево)
            106 => array(102=>3,  107=>2),
// беляево -(калужская , конькова )
            107 => array(106=>2,  105=>2),
// конькова -*беляево, тепоый стан)
            105 => array(107=>2,  103=>4),
// тепоый стан-( конькова  ясенево )
            103 => array(105=>4,  109=>3),
// ясенево -( тепоый стан- новоясеневскаяя )
            109 => array(103=>3,  108 =>2),
// новоясеневскаяя -(ясенево )
            108 => array(109=>2),


// красная ветка
//подбельского -(черкизовский)
            116 => array(117=>2),
// черкизовский -(подбельского преображенскя прощадь)
            117 => array(116=>2,124=>4),
// преображенскя прощадь -(черкизовский сокольники )
            124 => array(117=>4,126=>3),
// сокольники  -(преображенскя прощадь красносельска )
            126 => array(124=>3,125=>2),
// красносельска  -(сокольники  комсомольская )
            125 => array(126=>2,11=>2),
// комсомольская -( красносельска  комсомольская кольц, красные ворота)
            11 => array(125=>2,12=>&$t4,45=>2),
// красные ворота-( красносельска, чистые пруды )
            45 => array(11=>2,43=>1),
// чистые пруды -(красные ворота, сереневый,  тургеньевское лубянка    )
            43 => array(45=>1,179=>&$t2, 49=>&$t2,46=>2),
// лубянка -(чистые пруды, кущнцкий, охотный  )
            46 => array(43=>2,51=>&$t2, 44=>2),
// охотный  -(лубянка,  театральня, библиротека)
            44 => array(46=>2,152=>&$t3, 23=>2  ),
// библиротека -(охотный, боровитсяка, арабтская син, алекснаровский кропотненски)
        23 => array(44=>2,42=>&$t4, 156=>&$t3, 25=>&$t4, 39=>2  ),
// кропотненски-( библиротека  парт кульитуры)
        39 => array(23=>2,37=>2 ),
// парт кульитуры -(кропотненски, парк культуры кольц фрунзенчская)
        37=> array(39=>2,161=>&$t3 ,15=>3 ),
// фрунзенчская-( парт кульитуры  спортивная)
        15=> array(37=>3,91=>2 ),
// спортивная-( фрунзенчская воробьевы горц)
        91=> array(15=>2, 169=>3 ),
// воробьевы горц-( спортивная  университет)
        169=> array(91=>3, 93=>3 ),
// университет-( воробьевы горц вернацкого)
        93=> array(169=>3, 101=>3 ),
// вернацкого -(университет югозапалная)
        101=> array(93=>3, 100=>3 ),
// югозапалная-(университет)
        100=> array(101=>3),


     //кольцквая
      //БЕЛОРУССКАЯ кольц-(новослободская,БЕЛОРУССКАЯ зеленая   краснопреснч)
     153  => array(7=>2, 63=>&$t2, 61=>3),
     //новослоболская -(  БЕЛОРУССКАЯ кольц, мендеевская, проспект мира кольц )
     7  => array(153=>2,10=>&$t2, 6=>3),
     // проспект мира кольц  -(новослоболская,  комсомольская кольц , )
     6  => array(7=>3, 8=>&$t2,12=>3),
     // комсомольская кольц -( проспект мира кольц ,комсомольская кррасна, курская кольц )
     12  => array(6=>3, 11=>&$t4,13=>3),
     
     //повелекая кольцвая-(повелекая зеленая, таганка кольцевая, добрыненская
     32=>array(31=>&$t2,30=>3, 17=>3),
    //добрыненская-( СЕРПУХОВСКАЯ, повелекая кольцвая, октябрьская кольц 
    17=>array(20=>&$t2,32=>3, 35=>2),
    // октябрьская кольц  -(добрыненская- октябрьская кирпич, парк культуры кольц 
    35=>array(17=>2,162=>&$t2, 161=>2),
    // парк культуры кольц -=(октябрьская кольц, <strong> кольц</strong> киеввкся колььц  
    161=>array(35=>2,37=>&$t3, 38=>2),


     // глубая ветка
    //каховская-(севастопольская,варшавская)
    94=>array(98=>&$t0,92=>3),
//ааршавская -(каховская,кашрская голубая)
    92=>array(94=>3,154=>3),

//кашрская голубая-(кашрская зеленая, варшавская(
    154=>array(114=>&$t0,92=>3)

    );

   

?>

Это сообщение отредактировал(а) xber9 - 13.11.2012, 22:37

xber9

Дата 13.11.2012, 23:23 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 245
Регистрация: 21.1.2007

Репутация: нет
Всего: нет

офтоп
ошибочное сообщение

Это сообщение отредактировал(а) xber9 - 14.11.2012, 00:06

xber9

Дата 13.11.2012, 23:55 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 245
Регистрация: 21.1.2007

Репутация: нет
Всего: нет

такое ощущение что выбирает первый попавшийся путь а не путь с наименьшим весом

Это сообщение отредактировал(а) xber9 - 14.11.2012, 00:05

baldina

Дата 14.11.2012, 11:21 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

Репутация: 1
Всего: 101

Весь код покажите

xber9

Дата 14.11.2012, 11:42 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 245
Регистрация: 21.1.2007

Репутация: нет
Всего: нет

весь код ваш же полносью
вот

Код


    <?php 
include('mdata.php');


class BfsQueue {
  function __construct ($queue) {
    $this->q = $queue;
  }
  private $marks = array();
  function put ($v,$weight) {
    if (!$this->marks[$v]) {
      $this->q->enqueue($v,$weight);
      $this->marks[$v] = true;
    }
  }
  function get () {
      return $this->q->dequeue();
  }
  function isEmpty () {
      return $this->q->count() == 0;
  }
  function isVisited ($vw) {
      return $this->marks[$vw[0]];
  }
}

abstract class Graph {
  function __construct ($graph) {
    $this->graph = $graph;
  }

  abstract function getAdjacent ($v);
  abstract function getStart();
           function getWeight($v, $u) { return 1; }
}

// простая очередь на основе array()
class ArrayQueue {
  protected $q = array();
  function count() { return count($this->q); }
  function enqueue($e,$p) { $this->q[] = array($e,$p); }
  function dequeue() { return array_shift($this->q); }
}

abstract class Bfs {
  function __construct (Graph $graph, $queueClass='ArrayQueue') {
    $this->graph = $graph;
    $this->queueClass = $queueClass;
  }

  private function createQueue () { return new BfsQueue (new $this->queueClass); }

  protected function visitVertex($v,$weight) {}
  protected function visitEdge($v,$u,$weight) {}
  protected function getStart() { return $this->graph->getStart(); }

  function walk () {
     $queue = $this->createQueue();
     $queue->put ($this->getStart(),0);
     while (!$queue->isEmpty()) {
       list($v,$w) = $queue->get();
       $this->visitVertex ($v, $w);
       foreach ($this->graph->getAdjacent ($v) as $u) {
         if (!$queue->isVisited ($u)) {
           $w = $this->graph->getWeight($v, $u);
           $this->visitEdge ($v,$u,$w);
           $queue->put ($u,$w);
         }
       }
     }
  }
}

/**************************************************/

/*
// очередь с приоритетами на основе двоичной кучи spl
class PriorityQueue extends SplHeap {
  function compare ($v1, $v2) {
    return $v1[1] - $v2[1];
  }
  function enqueue($e,$weight) { $this->insert(array($e,$weight)); }
  function dequeue() { return $this->extract(); }
}
*/

// неэффективная очередь с приоритетами на основе array, трудоемкость извлечения O(n)

class PriorityQueue extends ArrayQueue {
  function dequeue() { 
    reset ($this->q);
    $key = key ($this->q);
    while ($c = next($this->q)) {
      if ($c[1] < $this->q[$key][1]) {
        $key = key ($this->q);
      }
    }
    $c = $this->q[$key];
    unset ($this->q[$key]);
    return $c;
  }
}

// класс поиска кратчайших путей алгоритмом Дейкстры
class DijkstraShortestPaths extends Bfs {
  function __construct ($graph) {
    parent::__construct ($graph, 'PriorityQueue');
  }
  protected function visitEdge($v,$u) {
    $w = $this->cost[$v]+$this->graph->getWeight($v, $u);
    if (!isset($this->cost[$u]) || $this->cost[$u] > $w) {
      $this->cost[$u] = $w;
      $this->path[$u] = $v;
    }
  }

  protected function getStart() { return $this->start; }

  function walk ($start) {
    $this->cost = array();
    $this->path = array();
    $this->cost[$this->start=$start] = 0;
    parent::walk();
  }
  function getPath($to) {
    while (isset($this->cost[$to])) {
      $path[] = $to;
      $to = $this->path[$to];
    }
    return is_array($path) ? array_reverse ($path) : false;
  }
  function getVes($to) {
    
    return $this->cost[$to];
  }
}

/**************************************************/
// адаптер графа для массива вида array(вершина=>array(соседняя вершина=>вес,...),...)
class ArrayGraph extends Graph {
  function __construct ($graph) {
    parent::__construct ($graph);
  }
  function getAdjacent ($v) {
    return isset($this->graph[$v]) ? array_keys($this->graph[$v]) : array();
  }
  function getStart() {
    reset ($this->graph);
    return key ($this->graph);
  }
  function getWeight($v, $u) { 
    return $this->graph[$v][$u]; 
  }
}



    if (isset($_GET['from']) && isset($_GET['to']) && isset($_GET['action'])) 
    {
      if (in_array($_GET['from'], array_keys($graph)) &&  in_array($_GET['to'], array_keys($graph))) 
      {
    if($_GET['action']==1){
    $t0=101;
$t1=102;
$t2=103;
$t3=104;
$t4=105;
     
        }
    

$from = $_GET['from'];
$to = $_GET['to'];
$gp = new DijkstraShortestPaths (new ArrayGraph($graph));
$gp->walk($from);
$path = $gp->getPath ($to);
$time= $gp->getVes($to); 


$out='{"routes":{"from":"'.$from.'","to":"'.$to.'","time":'.$time.',"transfers":1,"waypoints":[';

//     echo($out);
     foreach($path as $station) {

$out.='"'.$station.'",';
     }
$out=substr($out, 0, strlen($out)-1);     
     $out.=']}}';
     echo($out);
      } else { 
   echo(' 400');
       }
      } ?>

то что инклюдит это те данные что привел выще

если надо то от страницы делаю запрос на jquary так

Код


            e.ajax({
           
     url: "/metro/ROTES.php",
                data: {                    
                    from: this.from,
                    to: this.to,
            action: act
                },
                dataType: "json",
                type: "GET",
                success: function(i){                    
                    h.onSuccess(i.routes)                    
                },
                error: function(i){
                    e(h).trigger("Error")
                }
            })

Это сообщение отредактировал(а) xber9 - 14.11.2012, 11:46

baldina

Дата 15.11.2012, 17:08 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

Репутация: 1
Всего: 101

да, у меня ошибка. не тот приоритет передавался в очередь.
поглядите
http://codepad.org/qB803rhG

xber9

Дата 15.11.2012, 22:04 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 245
Регистрация: 21.1.2007

Репутация: нет
Всего: нет

работает отлично - большое спс
но хотелось бы понять что было не так - я все еще пытаюсь разобраться как это все работает

baldina

Дата 16.11.2012, 15:12 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

Репутация: 1
Всего: 101

не так был приоритет узла в очереди: передавался вес последнего ребра, а надо было передавать вес всего пути.
сравните код, поймете

Добавлено через 9 минут и 49 секунд
теперь вам надо очередь перевести на SplHeap или свою пирамиду написать: http://ru.wikipedia.org/wiki/%D0%94%D0%B2%...%83%D1%87%D0%B0

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| PHP: Для профи \| Следующая тема »

Внимание: данный раздел предназначен для решения сложных, нестандартных задач.