Меню
Что нового?

реализация алгоритма дейкстры для взвешанного графа

xber9

Новичок
народ привет
есть такая задача реализация алгоритма дейкстры для НЕ взвешанного графа
граф представлен как списки смежности
вот реалиция
PHP: 
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);
     }
 }
}

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

// адаптер для данной структуры графа
function get_adjacent ($graph, $v) {
  return isset($graph[$v]) ? $graph[$v] : array();
}

function print_node ($v, $u) {
  if ($v)
    echo $v,'->',$u, PHP_EOL;
}

// print all vertices
echo 'Ребра в порядке обхода в ширину:', PHP_EOL;
bfs($graph, 55, 'print_node');

// shortest paths
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;
  }
}

bfs($graph, 55, 'dijkstra_visitor');
echo PHP_EOL, 'Кратчайший путь из 55 в 164:', PHP_EOL;
var_dump ($path[164]);
я же хочу ввести в списки смежности, веса то есть наример так

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

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

rotoZOOM

ACM maniac
Дейкстры на НЕ взвешанном графе не бывает. Дейкстра по определению ищет кратчайший путь от одной вершины до всех остальных во взвешанном графе с неотрицательными весами. Так что в твоем частном случае вес ребер равен 1.

P.S. и вообще, у тебя не Дейкстра, а обычный bfs, читай внимательно алгоритм.
 

xber9

Новичок
rotoZOOM написал(а):
Дейкстры на НЕ взвешанном графе не бывает. Дейкстра по определению ищет кратчайший путь от одной вершины до всех остальных во взвешанном графе с неотрицательными весами. Так что в твоем частном случае вес ребер равен 1.

P.S. и вообще, у тебя не Дейкстра, а обычный bfs, читай внимательно алгоритм.
Нажмите для раскрытия...
ну пусть так
а как это все для дейкстры переделать
у меня мозгов не хватат((
 
Войдите или зарегистрируйтесь для ответа.
Сверху