Поиск кратчайшего пути

Andrew_P

Новичок
Поиск кратчайшего пути

Есть таблица в MySQL, в которй содержатся возможные маршруты, формата from_id | to_id.

Задача:
Найти кратчайший путь между заданными $start_id и $finish_id.

Вывод должен быть такой:
1. id1 = $start_id,
2. id2,
...
n. idn,
n1. idn1 = $finish_id

Подскажите, плиз?

Схематичное изображение (таблица маршрутов - связи точек на схеме):
 

Andrew_P

Новичок
Да, и при этом можно двигаться как от from_id -> to_id, так и наоборот to_id -> from_id.
 

Andrew_P

Новичок
2 Dovg, ты прикалываешься? Или как?

"рекурсия" - если вопрос, то ответ "мне все равно".
"рекурсия" - если предложение "нужен исходный код на PHP"
 

Andrew_P

Новичок
Re: Поиск кратчайшего пути

Dovg - вообще не понятно что хотел :(
AP - ничем не помог (поиском я пользоваться умею)
.des. - спасибо, но это MSSQL - не подходит и очень долго выполняется.

Решение грубо:
PHP:
 <tr class=table_text><td>
Прокладка маршрутов - тестирование<br>
<br>
 Airaken -> Meimungen
30000185    30003403
<br><br>

<?php

  function get_SSName($id) {
    $query =
      "select name ".
      "from solarSystems ".
      "where ".
      "  id = '".$id."'";
    $result = mysql_ask($query);
    $records_count = mysql_num_rows($result);
  
    if ($records_count > 0) {
      $row = mysql_fetch_array($result);
      $name = $row["name"];
    } else {
      $name = "";
    }
    
    return $name;
  }

  function get_NextSSids($id) {
    $query =
      "select from_s, to_s from routes ".
      "where ".
      "  from_s = ".$id." or to_s = ".$id;
    $result = mysql_ask($query);
    $records_count = mysql_num_rows($result);
  
    $SS = array();
    for ($i = 1; $i < $records_count + 1; $i++) {
      $row = mysql_fetch_array($result);

      if ($row["to_s"] == $id) {
        $SS[] = $row["from_s"];
      } else {
        $SS[] = $row["to_s"];
      }
    }

    return $SS;
  }
  
  function is_SSEn($id) {
    global $jumps;

    $find_en = false;  

    foreach($jumps as $i => $value) {
      if ($jumps[$i]["id"] == $id) {
        $find_en = true;
        break;  
      }
    }  

    return $find_en;
  }

  $start_system_id = 30000185;
  $finish_system_id = 30003403;

  $find_en = false;  
  $jumps = array(1 => array("id" => $start_system_id, "name" => get_SSName($start_system_id), "parent" => null));
  
  $jump = 1;
  while ($find_en == false) {
  
    $SS = get_NextSSids($jumps[$jump]["id"]);
    foreach($SS as $i => $value) {
      if (is_SSEn($SS[$i]) == false) {
//        echo $SS[$i]."<br>";
        $jumps[] = array("id" => $SS[$i], "name" => get_SSName($SS[$i]), "parent" => &$jumps[$jump]);
        if ($SS[$i] == $finish_system_id) {
          $find_jump_arr = &$jumps[$jump + 1];
          $find_en = true;
          break;  
        }
      }
    }  

    $jump++;
  }
    
  while ($find_jump_arr["parent"] != null) {
    echo "id = ".$find_jump_arr["parent"]["id"].", name = ".$find_jump_arr["parent"]["name"]."<br>";
  
    $find_jump_arr = $find_jump_arr["parent"];
  }

//  echo "<pre>";
//  print_r($jumps);
//  echo "</pre>";

?>

  </td></tr>
-~{}~ 26.01.07 18:17:

Теперь вопрос: как сделать массив маршрутов, так чтобы каждый поиск равнялся одной итерации?
 
Сверху