sidef-scripts/Graph/dijkstra_s_algorithm.sf

#!/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")