Forum PHP.pl

Witam wszystkich, potrzebuję napisać skrypt.
Treść zadania:
- na mapie Polski wybierz 49 dawnych miast wojewódzkich
- przypisz każdemu miastu kod (np nr 1-49)
- zobacz z iloma sąsiednimi miastami każde miasto ma bezpośrednie połączenie drogowe (ile km), przeciętnie jest połączenie z 3 do 8 miast
- wybierz miasto początkowe i miasto końcowe
- znajdź trasę łącząca wybrane miasta tak aby droga była najkrótsza

Czy ktoś mógłby mnie jakoś nakierować jak mógłbym to zrobić?



Algorytm Dijkstry, Forda-Bellmana, problem komiwojażera, Ant System(mrówkowy), Traveling Salesman Problem(TSP), Ant Colony Optimisation(ACO)...

I w czym problem? Mamy to zrobić za Ciebie? Mala pomoc:

[PHP] pobierz, plaintext 
<?php
/*
przykładowy graf:
 
       B-------C
      / \   1   \
   2 /   \       \5
    /     \       \
   A       \4      F
    \       \     /
   3 \       \   /1
      \       \ /
       D-------E
           2
 
autor skryptu: venaas <venaas () nvg ! ntnu ! no>
źródło: <a href="http://marc.theaimsgroup.com/?l=php-general&m=96024323421478&w=2" target="_blank">http://marc.theaimsgroup.com/?l=php-genera...3421478&w=2</a>
*/
 
$wezel["A"] = array("B"=>2, "D"=>3);
$wezel["B"] = array("A"=>2, "C"=>1, "E"=>4);
$wezel["C"] = array("B"=>1, "F"=>5);
$wezel["D"] = array("A"=>3, "E"=>2);
$wezel["E"] = array("D"=>2, "B"=>4, "F"=>1);
$wezel["F"] = array("C"=>5, "E"=>1);
 
function dijkstra($wezel, $start) {
  $closest = $start;
  while(isset($closest)) {
    $marked[$closest] = 1;
    reset($wezel[$closest]);
    while(list($vertex, $distance) = each($wezel[$closest])) {
      if ($marked[$vertex]) continue;
      $dist = $paths[$closest][0] + $distance;
      if (!isset($paths[$vertex]) || $dist<$paths[$vertex][0]) {
        $paths[$vertex] = $paths[$closest];
        $paths[$vertex][0] = $dist;
        $paths[$vertex][1] .= "$closest ";
      }
    }
    unset($closest);
    reset($paths);
    while(list($vertex, $path) = each($paths)) {
      if ($marked[$vertex]) continue;
      $distance = $path[0];
      if ($distance<$min || !isset($closest)) {
        $min = $distance;
        $closest = $vertex;
      }
    }
  }
  return $paths;
}
 
$start = "F"; // punkt od którego startujesz
 
$sciezki = dijkstra($wezel, $start);
ksort($sciezki);
foreach ($sciezki as $wezel => $sciezka) {
  echo "$start=&gt;$wezel: <b>$sciezka[0]</b>
        scieżka: [$sciezka[1] $wezel]<br />\n";
}
?>
[PHP] pobierz, plaintext 

Czy poza odległością ma być uwzględniane coś jeszcze (np. prędkość poruszania się po danej drodze)? Do poczytania:
a) teoria grafów (wystarczą kompletne podstawy)
(IMG:style_emoticons/default/cool.gif) problem najkrótszej trasy / ścieżki / drogi

Na prawdę w sieci są dziesiątki gotowych rozwiązań z wyczerpującymi opisami.

Nie nie, tylko odległość.

Wiele szukałem, ale nie znalazłem nic co rozwiązało mój problem.
Można jakieś linki?

Nie wierzę, że pod tym linkiem: graf najkrótsza droga, nie ma niczego co by rozwiązało Twój problem.