Dijkstra's 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}"

Output:

26 acde