Anonymous user
Dijkstra's algorithm: Difference between revisions
→{{header|Icon}} and {{header|Unicon}}
Line 973:
discovered.
<lang unicon>
global qMice, goodMice, region, qMiceEmpty
record Graph(nodes,weights)
record Node(name,targets,
record Path(weight, nodes)
Line 983:
graph := getGraph()
repeat {
writes("What is the start node? ")
start := \graph.nodes[read()] | stop()
writes("What is the finish node? ")
finish := read() | stop()
waitForCompletion() # block until all quantum mice have finished
showPath(getBestMouse(),start.name,finish)
cleanGraph(graph)
goodMice := set()
}
end
Line 1,009 ⟶ 1,014:
}
return graph
end
procedure cleanGraph(graph)
every (!graph.nodes).weight := &null
end
Line 1,014 ⟶ 1,023:
if \mouse then {
path := mouse.getPath()
every writes(" ",!path.nodes)
write()
Line 1,023 ⟶ 1,031:
# A "Quantum-mouse" for traversing graphs.
class QMouse(graph, loc, finish, path, mouse)
method addPath(n); put(path, n); end
method getPath(); return path; end
method atEnd(); return (finish == loc.name); end
method visit(n) #
newWeight := path.weight + graph.weights[loc.name||":"||n.name]
critical region[n]: if /n.weight | (newWeight < n.weight) then {
Line 1,043 ⟶ 1,051:
region := table()
every region[n := !g.nodes] := mutex()
qMice := set()
insert(qMice, self)▼
}
graph := g
loc := l
finish := f
/
if *path.nodes > 0 then
path.weight +:= g.weights[path.nodes[-1]||":"||loc.name]
put(path.nodes, loc.name)
mouse := thread {
if atEnd() then insert(goodMice, self) # This mouse found a finish
delete(qMice, self) # Kill this mouse
if *qMice=0 then signal(qMiceEmpty) # All mice are dead
}
end
Line 1,072 ⟶ 1,081:
procedure waitForCompletion()
critical qMiceEmpty: while *qMice > 0 do wait(qMiceEmpty)
end
</lang>
Sample run:
Line 1,091 ⟶ 1,101:
What is the start node? a
What is the finish node? f
Weight: 11 -> a c f
Best path from a to f has weight: 11▼
What is the start node? a
What is the finish node? e
Weight: 26 -> a c d e
What is the start node? f
What is the finish node? a
What is the start node?
->
</pre>
| |||