Dijkstra's algorithm: Difference between revisions
Content deleted Content added
→{{header|C}}: Make the heap functions unaware of the graph |
m Added Sidef |
||
Line 2,661: | Line 2,661: | ||
{{out}} |
{{out}} |
||
<pre>(26.0,List(a, c, d, e))</pre> |
<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}}== |
=={{header|Tcl}}== |