Dijkstra's algorithm: Difference between revisions
Content deleted Content added
No edit summary |
|||
Line 1,843: | Line 1,843: | ||
let path = shortest_path_to 'e' ' ' previous |
let path = shortest_path_to 'e' ' ' previous |
||
putStrLn $ "Path: " ++ show path</lang> |
putStrLn $ "Path: " ++ show path</lang> |
||
=={{header|Huginn}}== |
|||
<lang huginn>import Algorithms as algo; |
|||
import Mathematics as math; |
|||
import Text as text; |
|||
class Edge { |
|||
_to = none; |
|||
_name = none; |
|||
_cost = none; |
|||
constructor( to_, name_, cost_ ) { |
|||
_to = to_; |
|||
_name = name_; |
|||
_cost = real( cost_ ); |
|||
} |
|||
to_string() { |
|||
return ( "{}<{}>".format( _name, _cost ) ); |
|||
} |
|||
} |
|||
class Path { |
|||
_id = none; |
|||
_from = none; |
|||
_cost = none; |
|||
_names = none; |
|||
constructor( toName_, ids_, names_ ) { |
|||
_id = ids_[toName_]; |
|||
_names = names_; |
|||
_cost = math.INFINITY; |
|||
} |
|||
less( other_ ) { |
|||
return ( _cost < other_._cost ); |
|||
} |
|||
update( from_, cost_ ) { |
|||
_from = from_; |
|||
_cost = cost_; |
|||
} |
|||
to_string() { |
|||
return ( "{} via {} at cost {}".format( _names[_id], _from != none ? _names[_from] : none, _cost ) ); |
|||
} |
|||
} |
|||
class Graph { |
|||
_neighbours = []; |
|||
_ids = {}; |
|||
_names = []; |
|||
add_node( name_ ) { |
|||
if ( name_ ∉ _ids ) { |
|||
_ids[name_] = size( _names ); |
|||
_names.push( name_ ); |
|||
} |
|||
} |
|||
add_edge( from_, to_, cost_ ) { |
|||
assert( ( from_ ∈ _ids ) && ( to_ ∈ _ids ) ); |
|||
from = _ids[from_]; |
|||
to = _ids[to_]; |
|||
if ( from >= size( _neighbours ) ) { |
|||
_neighbours.resize( from + 1, [] ); |
|||
} |
|||
_neighbours[from].push( Edge( to, to_, cost_ ) ); |
|||
} |
|||
shortest_paths( from_ ) { |
|||
assert( from_ ∈ _ids ); |
|||
from = _ids[from_]; |
|||
paths = algo.materialize( algo.map( _names, @[_ids, _names]( name ) { Path( name, _ids, _names ); } ), list ); |
|||
paths[from].update( none, 0.0 ); |
|||
todo = algo.sorted( paths, @(x){-x._cost;} ); |
|||
while ( size( todo ) > 0 ) { |
|||
node = todo[-1]._id; |
|||
todo.resize( size( todo ) - 1, none ); |
|||
if ( node >= size( _neighbours ) ) { |
|||
continue; |
|||
} |
|||
neighbours = _neighbours[node]; |
|||
for ( n : neighbours ) { |
|||
newCost = n._cost + paths[node]._cost; |
|||
if ( newCost < paths[n._to]._cost ) { |
|||
paths[n._to].update( node, newCost ); |
|||
} |
|||
} |
|||
todo = algo.sorted( todo, @(x){-x._cost;} ); |
|||
} |
|||
return ( paths ); |
|||
} |
|||
path( paths_, to_ ) { |
|||
assert( to_ ∈ _ids ); |
|||
to = _ids[to_]; |
|||
p = [to_]; |
|||
while ( paths_[to]._from != none ) { |
|||
to = paths_[to]._from; |
|||
p.push( _names[to] ); |
|||
} |
|||
return ( algo.materialize( algo.reversed( p ), list ) ); |
|||
} |
|||
to_string() { |
|||
s = ""; |
|||
for ( i, n : algo.enumerate( _neighbours ) ) { |
|||
s += "{} -> {}\n".format( _names[i], n ); |
|||
} |
|||
} |
|||
} |
|||
main() { |
|||
g = Graph(); |
|||
confStr = input(); |
|||
if ( confStr == none ) { |
|||
return ( 1 ); |
|||
} |
|||
conf = algo.materialize( algo.map( text.split( confStr ), integer ), tuple ); |
|||
assert( size( conf ) == 2 ); |
|||
for ( _ : algo.range( conf[0] ) ) { |
|||
line = input(); |
|||
if ( line == none ) { |
|||
return ( 1 ); |
|||
} |
|||
g.add_node( line.strip() ); |
|||
} |
|||
for ( _ : algo.range( conf[1] ) ) { |
|||
line = input(); |
|||
if ( line == none ) { |
|||
return ( 1 ); |
|||
} |
|||
g.add_edge( algo.materialize( text.split( line.strip() ), tuple )... ); |
|||
} |
|||
print( string( g ) ); |
|||
paths = g.shortest_paths( "a" ); |
|||
for ( p : paths ) { |
|||
print( "{}\n".format( p ) ); |
|||
} |
|||
print( "{}\n".format( g.path( paths, "e" ) ) ); |
|||
print( "{}\n".format( g.path( paths, "f" ) ) ); |
|||
}</lang> |
|||
=={{header|Icon}} and {{header|Unicon}}== |
=={{header|Icon}} and {{header|Unicon}}== |