Dijkstra's algorithm: Difference between revisions

← Older edit Newer edit →

Content deleted Content added

Inline

@@ Line 1,843: / Line 1,843: @@
   let path = shortest_path_to 'e' ' ' previous
   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}}==