Форум программистов [Powered by Invision Power Board]

Код


    <?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');
       }
      } ?>

Цитата

count($newpath) < count($shortest)

Код


path_length($newpath) < path_length($shortest)

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

)

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

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

)

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

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

)

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

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

)

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

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

)

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

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

)

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

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

)

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

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

)

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

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

)

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

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

)

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

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

)

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

Код


    

//---------------------------------------------------------------------------
//Алгоритм Дейкстры.поиска кратчайшего пути
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.*/
 
//---------------------------------------------------------------------------

Код


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);
     }
 }
}

Код


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;
  }
}

Код


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

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

)

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

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

)

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

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

)

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

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

)

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

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

)

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

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

)

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

Цитата(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:41

)

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

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

)

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

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

)

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

Код


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);
     }
 }
}

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

)

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

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

)

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

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

)

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

Код


$this->cost[$to];

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

)

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

Код


$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),
);

Код



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

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

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

}

Код


$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;

Цитата

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

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

)

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

Код


<?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)

    );

   

?>

Код


    <?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');
       }
      } ?>

Код


            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")
                }
            })