123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101 |
- #!/usr/bin/ruby
- #
- ## https://rosettacode.org/wiki/Dijkstra%27s_algorithm
- #
- class Graph(*args) {
- struct Node {
- String name,
- Array edges = [],
- Number dist = Inf,
- Node 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}"
- assert_eq(g.get('e').dist, 26)
- assert_eq(path, "acde")
|