Šiandien atsiverčiau sąsiuvinį ir mėginau iš atminties prisiminti Dijkstra algoritmą. Pasipaišiau vieną jungųjį grafą su keliais ciklais, be pasikartojančių briaunų ir briaunų, jungiančių tą pačią viršūnę. Nuskaitomas grafas kaip eilučių iš trijų duomenų laukų rinkinys: [viršūnė], [viršūnė], [briaunos svoris (kaina)]. Pradžioj iki galo nesupratau, kaip turėtų elgtis algoritmas ir ėmiau rašyti kažką panašaus į paiešką į plotį (bfs). Vėliau pamačiau, kad, reikia pirmenybę skirti mažiausią kainą turinčiai viršūnei, kuri gali būti paėjusi nuo pradinės viršūnės tolėliau, tai tą ilgokai rašiausi.
Apskritai Dijkstros algoritmas yra algoritmas, kurio rezultatas tai yra pigiausi (nebūtinai trumpiausi) keliai tarp vienos pasirinktos grafo viršūnės ir visų kitų viršūnių. Jis pradeda veikti nuo pasirinktos viršūnės ir plečiasi briaunomis link kitų viršūnių ir jose saugo einamąjį minimalųjį svorį (kainą), o plėtimosi frontas - visada ties pigiausiai pasiekiama viršūne, kuri jau buvo aplankyta.
Galiausiai parašiau kažką panašaus į minimą algoritmą, tik algoritminis sudėtingumas atrodo nesutvarkytas iki galo, ir programa turėtų veikti lėtai prie didesnių duomenų. Pirmoj įvesties eilutėj - dvi viršūnės: iš kurios į kurią nueit. Išveda -1, jeigu pasiekti neįmanoma, o jei įmanoma - išveda maršrutą. Viršūnės pažymėtos numeriais, nors gali būti ir raidės/žodžiai.
use warnings;
use strict;
while(<DATA>){
my ($n, $m) = (split);
my %h = ();
my $maxw = 1e7;
for (<DATA>){
my ($v, $d, $w) = split;
$h{ $v }{neib} //= [];
$h{ $d }{neib} //= [];
$h{ $v }{ $d } = $w ;
$h{ $d }{ $v } = $w ;
$h{ $v }{weight} = $maxw;
$h{ $d }{weight} = $maxw;
push @{ $h{ $v }{neib} }, $d;
push @{ $h{ $d }{neib} }, $v;
}
$h{ $n }{weight} = 0;
$h{ $n }{from} = -1;
my @arr = ($n);
while (@arr){
my $min = $maxw;
my $min_node;
$min > $h{ $_ }{weight} and
($min = $h{ $_ }{weight}, $min_node = $_)
for @arr;
my $node = $min_node;
@arr = grep $_ != $min_node, @arr;
push @arr, grep $h{ $_ }{weight} == $maxw,
@{ $h{ $node }{neib} };
for my $neib ( @{ $h{ $node }{neib} } ){
$neib == $h{ $node }{from} and next;
if ($h{ $neib }{weight} >
$h{ $node }{weight} + $h{ $neib }{ $node }
)
{
$h{ $neib }{weight} =
$h{ $node }{weight} + $h{ $neib }{ $node };
$h{ $neib }{from} = $node;
}
}
}
my @ans = ($m);
$h{ $m }{from} // (@ans = (-1));
while ( $ans[0] != -1 and $h{ $m }{from} > -1 ){
push @ans, $m = $h{ $m }{from};
}
@ans = reverse @ans;
print "@ans";
}
__DATA__
11 2
1 2 88
4 1 10
4 3 10
5 4 10
1 7 45
8 7 10
9 8 15
10 8 10
8 11 50
9 4 5
11 7 10
