Примеры
Вариант 1. Дана сеть автомобильных дорог, соединяющих города Новосибирской области. Некоторые дороги односторонние. Найти кратчайшие пути от Новосибирска до каждого города области (если двигаться можно только по дорогам).
Вариант 2. Имеется некоторое количество авиарейсов между городами мира, для каждого известна стоимость. Стоимость перелёта из A в B может быть не равна стоимости перелёта из B в A. Найти маршрут минимальной стоимости (возможно, с пересадками) от Копенгагена до Барнаула.
class dilizhans {
public $arrput;
public $cena;
}
class rebro {
public $nach_tochka;
public $kon_tochka;
public $cena_rebra;
}
$mas = file_get_contents ('C:\Users\Антон\Desktop\rebra.txt');
$arr_rebra = explode("\n",$mas);
for($i=0;$i<count($arr_rebra);$i=$i+4)
{
$graf[] = new rebro();
$graf[count($graf)-1]->nach_tochka=$arr_rebra[$i];
$graf[count($graf)-1]->kon_tochka=$arr_rebra[$i+1];
$graf[count($graf)-1]->cena_rebra=$arr_rebra[$i+2];
}
//echo "<pre>";
//print_r($graf);
//echo "</pre>";
$work[] = new dilizhans();
$work[count($work)-1]->arrput[]=1;
$work[count($work)-1]->cena=0;
//echo "<pre>";
//print_r($work);
//echo "</pre>";
$i=0;
while ($i<20) {
$n=$work[$i]->arrput[count($work[$i]->arrput)-1];
if ($work[$i]->arrput[count($work[$i]->arrput)-1]<10)
{ for($j=0;$j<count($graf);$j++)
{
if($graf[$j]->nach_tochka==$n)
{
$work[] = new dilizhans();
$work[count($work)-1]->arrput=$work[$i]->arrput;
$work[count($work)-1]->arrput[]=$graf[$j]->kon_tochka;
$work[count($work)-1]->cena=$work[$i]->cena+$graf[$j]->cena_rebra;
}
}
$work[$i]->cena=0;
}
$i++;
}
for ($i=0;$i<count($work);$i++)
{
if ($work[$i]->arrput[count($work[$i]->arrput)-1]==10&&$work[$i]->cena!=0)
{var_dump($work[$i]);echo "<br>";}
}
Спустя 139 сек.
Информация в txt файле хранится в таком формате:1 - номер начальной точки
2 - номер конечной точки
1 - длинна ребра
1
3
2
1
4
3
2
5
3
2
3
3
3
6
6
3
7
4
4
7
9
5
8
5
5
6
2
6
8
7
6
9
1
7
9
1
8
10
9
9
10
3
