/
desopo-pape.jl
78 lines (66 loc) · 1.76 KB
/
desopo-pape.jl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
"""
struct DEposoPapeState{T, U}
An [`AbstractPathState`](@ref) designed for D`Esopo-Pape shortest-path calculations.
"""
struct DEsopoPapeState{T<:Real,U<:Integer} <: AbstractPathState
parents::Vector{U}
dists::Vector{T}
end
"""
desopo_pape_shortest_paths(g, src, distmx=weights(g))
Compute shortest paths between a source `src` and all
other nodes in graph `g` using the [D'Esopo-Pape algorithm](http://web.mit.edu/dimitrib/www/SLF.pdf).
Return a [`Graphs.DEsopoPapeState`](@ref) with relevant traversal information.
# Examples
```jldoctest
julia> using Graphs
julia> ds = desopo_pape_shortest_paths(cycle_graph(5), 2);
julia> ds.dists
5-element Vector{Int64}:
1
0
1
2
2
julia> ds = desopo_pape_shortest_paths(path_graph(5), 2);
julia> ds.dists
5-element Vector{Int64}:
1
0
1
2
3
```
"""
function desopo_pape_shortest_paths(
g::AbstractGraph, src::Integer, distmx::AbstractMatrix{T}=weights(g)
) where {T<:Real}
U = eltype(g)
nvg = nv(g)
(src in 1:nvg) || throw(DomainError(src, "src should be in between 1 and $nvg"))
dists = fill(typemax(T), nvg)
parents = zeros(U, nvg)
state = Vector{Int8}()
state = fill(Int8(2), nvg)
q = U[src]
@inbounds dists[src] = 0
@inbounds while !isempty(q)
u = popfirst!(q)
state[u] = 0
for v in outneighbors(g, u)
alt = dists[u] + distmx[u, v]
if (dists[v] > alt)
dists[v] = alt
parents[v] = u
if state[v] == 2
state[v] = 1
push!(q, v)
elseif state[v] == 0
state[v] = 1
pushfirst!(q, v)
end
end
end
end
return DEsopoPapeState{T,U}(parents, dists)
end