Dijkstra's algorithm: Difference between revisions
m
Added Sidef
(→{{header|C}}: Make the heap functions unaware of the graph) |
m (Added Sidef) |
||
Line 2,661:
{{out}}
<pre>(26.0,List(a, c, d, e))</pre>
=={{header|Sidef}}==
{{trans|Perl}}
<lang ruby>class Graph(*args) {
struct Node {
String name,
Array edges = [],
Number dist = Inf,
prev = nil,
Bool visited = false,
}
struct Edge {
Number weight,
Node vertex,
}
has g = Hash()
method init {
args.each { |a|
self.add_edge(a...)
}
}
method get(name) {
g{name}
}
method add_edge(a, b, weight) {
g{a} ||= Node(name: a)
g{b} ||= Node(name: b)
g{a}.edges << Edge(weight, g{b})
}
method push_priority(a, v) {
var i = 0
var j = a.end
while (i <= j) {
var k = ((i + j) // 2)
if (a[k].dist >= v.dist) {
j = k-1
}
else {
i = k+1
}
}
a.insert(i, v)
}
method dijkstra(a, b) {
g{a}.dist = 0
var h = []
self.push_priority(h, g{a})
while (!h.is_empty) {
var v = h.shift
break if (v.name == b)
v.visited = true
v.edges.each { |e|
var u = e.vertex
if (!u.visited && (v.dist+e.weight <= u.dist)) {
u.prev = v
u.dist = (v.dist + e.weight)
self.push_priority(h, u)
}
}
}
}
}
var g = Graph(
["a", "b", 7],
["a", "c", 9],
["a", "f", 14],
["b", "c", 10],
["b", "d", 15],
["c", "d", 11],
["c", "f", 2],
["d", "e", 6],
["e", "f", 9],
)
g.dijkstra('a', 'e')
var v = g.get('e')
var a = []
while (v != nil) {
a << v.name
v = v.prev
}
var path = a.reverse.join
say "#{g.get('e').dist} #{path}"</lang>
{{out}}
<pre>
26 acde
</pre>
=={{header|Tcl}}==
| |||