JuliaのDataStructures.jlを利用したDijkstra法の実装例(C++ -> Julia)

julia_dijkstra_example.jl

# -*- coding: utf-8 -*-

module Dijkstra

using DataStructures

mutable struct Edge
    to::Int
    cost::Int
end

V = 9
E = 14

g = Array{Array{Edge, 1}, 1}()
for v in 1:V
    push!(g, Array{Edge, 1}())
end

"""
Edge list
1 2 4
1 8 8
2 3 8
2 8 11
3 4 7
3 6 4
3 9 2
4 5 9
4 6 14
5 6 10
6 7 2
7 8 1
7 9 6
8 9 7
"""

for i in 1:E
    is = readline()
    is = parse.(Int, split(is))
    push!(g[is[1]], Edge(is[2], is[3]))
    push!(g[is[2]], Edge(is[1], is[3]))
end

using DataStructures

function dijkstra_from(s::Int)
    ans = zeros(Int, V)
    ans .= 1e7
    ans[s] = 0 

    q = PriorityQueue{Int, Int}()
    q[s] = 0

    while length(q) > 0
        mv, md = peek(q)
        dequeue!(q)
        (ans[mv] < md) && continue
        for i in 1:length(g[mv])
            edge = g[mv][i]
            if ans[edge.to] > ans[mv] + edge.cost
                ans[edge.to] = ans[mv] + edge.cost
                q[edge.to] = ans[edge.to]
            end
        end
    end

    return ans
end

ans = dijkstra_from(1)
println(ans)

end