Rosetta Code

Dijkstra's algorithm: Difference between revisions

Page Discussion

Dijkstra's algorithm (view source)

Revision as of 23:17, 22 February 2013

24 bytes removed ,  11 years ago
D entry: the graph is now directed
m (→‎{{header|PHP}}: fix array minimum finder)
(D entry: the graph is now directed)
Line 381:
 
=={{header|D}}==
This solution is incorrect. Since the path is directed and f is only a sink, f cannot be in the middle of a path.
{{trans|C++}}
The algorithm and the important data structures are essentially the same as in the C++ version, so the same comments apply (built-in D associative arrays are unsorted).
<lang d>import std.stdio, std.typecons, std.algorithm, std.container;
 
alias string Vertex = string;
alias int Weight = int;
 
const struct Neighbor {
Line 394 ⟶ 393:
}
 
alias AdjacencyMap = Neighbor[][Vertex] AdjacencyMap;
 
Tuple!(Weight[Vertex], Vertex[Vertex])
Line 403 ⟶ 402:
foreach (v, neighs; adjacencyMap) {
minDistance[v] = Weight.max;
foreach (immutable n; neighs)
minDistance[n.target] = Weight.max;
}
 
minDistance[source] = 0;
alias Pair = Tuple!(Weight, Vertex) Pair;
auto vertexQueue = redBlackTree(Pair(minDistance[source], source));
typeof(typeof(return)[1]) previous;
 
while (!vertexQueue.empty) {
const u = vertexQueue.front()[1];
vertexQueue.removeFront();
 
if (u == target)
break;
 
// Visit each edge exiting u.
foreachif (n;u in adjacencyMap[u]) {
const v =foreach (n.target; adjacencyMap[u]) {
const distanceThroughU = minDistance[u] +const v = n.weighttarget;
if ( const distanceThroughU <= minDistance[vu]) {+ n.weight;
vertexQueue.removeKey(Pairif (distanceThroughU < minDistance[v], v)); {
vertexQueue.removeKey(Pair(minDistance[v], = distanceThroughUv));
previous minDistance[v] = udistanceThroughU;
vertexQueue.insert(Pair(minDistance previous[v], v))= u;
vertexQueue.insert(Pair(minDistance[v], v));
}▼
}
▲ }
}
 
Line 452:
 
void main() {
AdjacencyMap adj;▼
immutable arcs = [tuple("a", "b", 7),
tuple("a", "c", 9),
Line 462 ⟶ 461:
tuple("d", "e", 6),
tuple("e", "f", 9)];
 
▲ AdjacencyMap adj;
foreach (arc; arcs) {
// Edges in both directions for an undirected graph▼
adj[arc[0]] ~= Neighbor(arc[1], arc[2]);
▲ // EdgesAdd inthis bothif directionsyou forwant an undirected graph:
//adj[arc[1]] ~= Neighbor(arc[0], arc[2]); //
}
 
Line 472 ⟶ 473:
const previous = minDist_prev[1];
 
writeln("`Distance from "a" to "e": "`, minDistance["e"]);
writeln("Path : ", dijkstraGetShortestPathTo("e", previous));
}</lang>
{{out}}
<pre>Distance from "a" to "e": 2026
Path : ["a", "c", "fd", "e"]</pre>
 
=={{header|Go}}==
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/209854"