Dijkstra's algorithm with adjacency matrix

Question

I'm trying to implement the following code from here but it won't work correctly.

What I want is the shortest path distances from a source to all nodes and also the predecessors. Also, I want the input of the graph to be an adjacency matrix which contains all of the edge weights.

I'm trying to make it work in just one function so I have to rewrite it. If I'm right the original code calls other functions (from graph.jl for example).

I don't quite understand how to rewrite the for loop which calls the adj() function.

Also, I'm not sure if the input is correct in the way the code is for now.

function dijkstra(graph, source)
    node_size = size(graph, 1)
    dist = ones(Float64, node_size) * Inf
    dist[source] = 0.0
    Q = Set{Int64}()  # visited nodes
    T = Set{Int64}(1:node_size)  # unvisited nodes
    pred = ones(Int64, node_size) * -1
    while condition(T)
        # node selection
        untraversed_nodes = [(d, k) for (k, d) in enumerate(dist) if k in T]
        if minimum(untraversed_nodes)[1] == Inf
            break # Break if remaining nodes are disconnected
        end
        node_ind = untraversed_nodes[argmin(untraversed_nodes)][2]
        push!(Q, node_ind)
        delete!(T, node_ind)
        # distance update
        curr_node = graph.nodes[node_ind]
        for (neigh, edge) in adj(graph, curr_node)
            t_ind = neigh.index
            weight = edge.cost
            if dist[t_ind] > dist[node_ind] + weight
                dist[t_ind] = dist[node_ind] + weight
                pred[t_ind] = node_ind
            end
        end
    end
    return dist, pred
end

So if I'm trying it with the following matrix

A = [0 2 1 4 5 1; 1 0 4 2 3 4; 2 1 0 1 2 4; 3 5 2 0 3 3; 2 4 3 4 0 1; 3 4 7 3 1 0] 

and source 2 i would like to get the distances in a vector dist and the predeccessors in anothe vectore pred.

Right now I'm getting

ERROR: type Array has no field nodes

Stacktrace: [1] getproperty(::Any, ::Symbol) at .\sysimg.jl:18

I guess I have to rewrite it a bit more.

I m thankful for any help.

Answer 1

Assuming that graph[i,j] is a length of path from i to j (your graph is directed looking at your data), and it is a Matrix with non-negative entries, where 0 indicates no edge from i to j, a minimal rewrite of your code should be something like:

function dijkstra(graph, source)
    @assert size(graph, 1) == size(graph, 2)
    node_size = size(graph, 1)
    dist = fill(Inf, node_size)
    dist[source] = 0.0
    T = Set{Int}(1:node_size)  # unvisited nodes
    pred = fill(-1, node_size)
    while !isempty(T)
        min_val, min_idx = minimum((dist[v], v) for v in T)
        if isinf(min_val)
            break # Break if remaining nodes are disconnected
        end
        delete!(T, min_idx)
        # distance update
        for nei in 1:node_size
            if graph[min_idx, nei] > 0 && nei in T
                possible_dist = dist[min_idx] + graph[min_idx, nei]
                if possible_dist < dist[nei]
                    dist[nei] = possible_dist
                    pred[nei] = min_idx
                end
            end
        end
    end
    return dist, pred
end

(I have not tested it extensively, so please report if you find any bugs)