# Graph.jl : How to interpret the output information returned by the shortest path algorithms?

**URL:** <https://discourse.julialang.org/t/graph-jl-how-to-interpret-the-output-information-returned-by-the-shortest-path-algorithms/94752>\
**Category:** Graphs\
**Tags:** question, package, lightgraphs, graphs\
**Created:** [February 16, 2023, 11:03pm UTC](https://discourse.julialang.org/t/graph-jl-how-to-interpret-the-output-information-returned-by-the-shortest-path-algorithms/94752 "2023-02-16T23:03:37Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![F\_A](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/f_a/32/53159_2.png) [@F\_A](https://discourse.julialang.org/u/F_A)\
**Post date:** [February 16, 2023, 11:03pm UTC](https://discourse.julialang.org/t/graph-jl-how-to-interpret-the-output-information-returned-by-the-shortest-path-algorithms/94752/1 "2023-02-16T23:03:37Z")

</div>

Hi there,

I’d like to use Graph.jl package to run a shortest path algorithm. I have already read this [page](https://juliagraphs.org/Graphs.jl/dev/algorithms/shortestpaths/#Graphs.DijkstraState) and am still not sure how to interpret the return traversal information of shortest path algorithm.  
Let’s assume I’m interested in three of these algorithm; bellman\_ford, dijkstra, and yen\_k.

Here’s a small example. A Weighted digraph with 5 nodes and 5 edges :

```julia
using SimpleWeightedGraphs
using Graphs
using SplitApplyCombine
using SparseArrays

sources = [1,1,3,3,4]
destinations = [2, 3,4,5,5]
weight = [3, 0.5,1,2,1]
g = SimpleWeightedDiGraph(sources, destinations, weight)
edges(g)
weights(g)

blfs = Graphs.bellman_ford_shortest_paths(g,1)
dijk = Graphs.dijkstra_shortest_paths(g,1)

yen = Graphs.yen_k_shortest_paths(g, 1, 5, weights(g))
yen2 = Graphs.yen_k_shortest_paths(g, 1, 5, weights(g), 2)
yen2max = Graphs.yen_k_shortest_paths(g, 1, 5, weights(g), 2;maxdist=10) # there's clearly other path 1>3>4>5 with the total distance of 2.5
astar = Graphs.a_star(g, 1, 5, weights(g))

```

What I receive after running `blfs = Graphs.bellman_ford_shortest_paths(g,1)` is:

```julia
Graphs.BellmanFordState{Float64, Int64}([0, 1, 1, 3, 3], [0.0, 3.0, 0.5, 1.5, 2.5])

```

What information do these two lists contain? And why we have `0` in them (when there’s no nodes labeled by `0`) ?

Same question for `dijk = Graphs.dijkstra_shortest_paths(g,1)`. The return output is:

```julia
Graphs.DijkstraState{Float64, Int64}([0, 1, 1, 3, 3], [0.0, 3.0, 0.5, 1.5, 2.5], [Int64[], Int64[], Int64[], Int64[], Int64[]], [1.0, 1.0, 1.0, 1.0, 2.0], Int64[])

```

\*----------------------------------------------------------------------------------------

According to documentation; the “yen\_k” Perform Yen’s algorithm, computing k-shortest distances between `source` and `target` other vertices. Return contains distances and paths.

When I ran it, however, it does not return “K” different path but K copy of the same path. Why?  
For instance:

`yen2 = Graphs.yen_k_shortest_paths(g, 1, 5, weights(g), 2)` returns:

```julia
Graphs.YenState{Float64, Int64}([2.5, 2.5], [[1, 3, 5], [1, 3, 5]])

```

Althogh there’s clearly other path 1\>3\>4\>5 with the total distance of 2.5 also. Why it just returns 1\>3\>5 instead?

Also `yen_k_shortest_paths`, what exactly `maxdist` control? Is it to have a limit over the shortest distance? if so, why `yen2max = Graphs.yen_k_shortest_paths(g, 1, 5, weights(g), 2;maxdist=10)` does not consider `10` at all?

One more question:  
How to run A\* algorithm? I’ve tried different things (like `astar = Graphs.a_star(g, 1, 5, weights(g))`), all of which returned an error.

```julia
ERROR: MethodError: no method matching SimpleWeightedEdge{Int64, Float64}(::Int64, ::Int64)

```

`a_star(g, s, t[, distmx][, heuristic][, edgetype_to_return])`

Thanks very much,  
F

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [February 17, 2023, 8:35am UTC](https://discourse.julialang.org/t/graph-jl-how-to-interpret-the-output-information-returned-by-the-shortest-path-algorithms/94752/2 "2023-02-17T08:35:48Z")

</div>

Hi @F_A!

First of all, I agree that the documentation for shortest paths is insufficient ([Insufficient documentation for shortest path functions · Issue #152 · JuliaGraphs/Graphs.jl · GitHub](https://github.com/JuliaGraphs/Graphs.jl/issues/152)), I’ll try to add more details soon.

What Dijkstra and Bellman-Ford do is not just find one shortest path from a source to a target: they find the shortest paths from a source to _all_ other vertices of the graph. This is easily stored as a shortest path tree spreading out from the source. All we need to remember is the parent of each vertex in the tree.

Let’s see how we can interpret the output thanks to the built-in REPL help mode:

```julia
julia> blfs = Graphs.bellman_ford_shortest_paths(g, 1)
Graphs.BellmanFordState{Float64, Int64}([0, 1, 1, 3, 3], [0.0, 3.0, 0.5, 1.5, 2.5])

help?> blfs
search: blfs blockfractions bellman_ford_shortest_paths enable_fzf GlobalRef

  No documentation found.

  blfs is of type Graphs.BellmanFordState{Float64, Int64}.

  Summary
  ≡≡≡≡≡≡≡≡≡

  struct Graphs.BellmanFordState{Float64, Int64}

  Fields
  ≡≡≡≡≡≡≡≡

  parents :: Vector{Int64}
  dists :: Vector{Float64}

  Supertype Hierarchy
  ≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡

  Graphs.BellmanFordState{Float64, Int64} <: Graphs.AbstractPathState <: Any

```

So apparently the resulting object has two fields: `parents` and `dists`. The former gives you the predecessor of each vertex in the shortest path coming from the source, while the latter gives you the distance between said vertex and the source.

```julia
julia> blfs.parents
5-element Vector{Int64}:
 0
 1
 1
 3
 3

julia> blfs.dists
5-element Vector{Float64}:
 0.0
 3.0
 0.5
 1.5
 2.5

```

Since we picked 1 as the source, it has no parent (that’s what the 0 means) and the distance to it is also 0.0. Unfortunately, you need to work a little more to retrieve the actual path to a vertex `v`, for instance with a utility function like this one (maybe we should include it in Graphs.jl):

```julia
julia> function get_path(blfs::Graphs.BellmanFordState, v::Integer)
           u = v
           path = [u]
           while blfs.parents[u] != 0
               u = blfs.parents[u]
               pushfirst!(path, u)
           end
           return path
       end
get_path (generic function with 1 method)

julia> get_path(blfs, 1)
1-element Vector{Int64}:
 1

julia> get_path(blfs, 2)
2-element Vector{Int64}:
 1
 2

julia> get_path(blfs, 4)
3-element Vector{Int64}:
 1
 3
 4

```

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [February 17, 2023, 8:41am UTC](https://discourse.julialang.org/t/graph-jl-how-to-interpret-the-output-information-returned-by-the-shortest-path-algorithms/94752/3 "2023-02-17T08:41:39Z")

</div>

Regarding Yen’s algorithm:

- you get identical paths because of an issue in SimpleWeightedGraphs.jl ([[Port] [BUG] `yen_k_shortest_paths` with `k=2` returns same path twice · Issue #42 · JuliaGraphs/Graphs.jl · GitHub](https://github.com/JuliaGraphs/Graphs.jl/issues/42) and [[Port] Removing an edge just sets the edge weight to 0 · Issue #6 · JuliaGraphs/SimpleWeightedGraphs.jl · GitHub](https://github.com/JuliaGraphs/SimpleWeightedGraphs.jl/issues/6)) which will soon be fixed thanks to a PR by @etienne_dg ([rework of weighted graphs API, fixes #6 and Graphs#42 by etiennedeg · Pull Request #14 · JuliaGraphs/SimpleWeightedGraphs.jl · GitHub](https://github.com/JuliaGraphs/SimpleWeightedGraphs.jl/pull/14))
- the `maxdist` argument is ignored because of an issue in Graphs.jl itself ([[PORT] [BUG] yen\_k\_shortest\_paths always returns at least one path · Issue #103 · JuliaGraphs/Graphs.jl · GitHub](https://github.com/JuliaGraphs/Graphs.jl/issues/103)), there is a PR by @aurorarossi which I’ll try to review ([Solved bug in yen.jl by aurorarossi · Pull Request #183 · JuliaGraphs/Graphs.jl · GitHub](https://github.com/JuliaGraphs/Graphs.jl/pull/183))

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [February 17, 2023, 9:08am UTC](https://discourse.julialang.org/t/graph-jl-how-to-interpret-the-output-information-returned-by-the-shortest-path-algorithms/94752/4 "2023-02-17T09:08:13Z")

</div>

Finally, for A\*, the issue is that the output is a vector of edges, but SimpleWeightedGraphs does not know how to construct an edge based on source and destination alone, it also needs a weight. This has given rise to lengthy discussions ([Fix A\* implementation by gdalle · Pull Request #125 · JuliaGraphs/Graphs.jl · GitHub](https://github.com/JuliaGraphs/Graphs.jl/pull/125)), and in the long term we probably need to change the way edges are handled by Graphs.jl as a whole (for instance with a `get_edge(g, s, d)` method. Feel free to contribute to the roadmap ([Roadmap for Graphs.jl 2.0 · Issue #128 · JuliaGraphs/Graphs.jl · GitHub](https://github.com/JuliaGraphs/Graphs.jl/issues/128)).  
In the meantime, the solution is to tell `a_star` that it should return a vector of `SimpleEdge` instead, as detailed in the docs:

```julia
help?> a_star
search: a_star spectral_distance watts_strogatz spfa_shortest_paths make_edgestream

  a_star(g, s, t[, distmx][, heuristic][, edgetype_to_return])

  Compute a shortest path using the A* search algorithm
  (http://en.wikipedia.org/wiki/A%2A_search_algorithm).

  Arguments
  ≡≡≡≡≡≡≡≡≡≡≡

    • g::AbstractGraph: the graph

    • s::Integer: the source vertex

    • t::Integer: the target vertex

    • distmx::AbstractMatrix: an optional (possibly sparse) n × n matrix of
       edge weights. It is set to weights(g) by default (which itself falls
       back on Graphs.DefaultDistance).

    • heuristic::Function: an optional function mapping each vertex to a
       lower estimate of the remaining distance from v to t. It is set to v
       -> 0 by default (which corresponds to Dijkstra's algorithm)

    • edgetype_to_return::Type{E}: the eltype E<:AbstractEdge of the vector
       of edges returned. It is set to edgetype(g) by default. Note that the
       two-argument constructor E(u, v) must be defined, even for weighted
       edges: if it isn't, consider using E = Graphs.SimpleEdge.

```

And indeed, the following change works:

```julia
julia> distmx = weights(g);

julia> heuristic(v) = zero(eltype(distmx));

julia> edgetype_to_return = Graphs.SimpleEdge;

julia> astar = Graphs.a_star(g, 1, 5, distmx, heuristic, edgetype_to_return)
2-element Vector{Graphs.SimpleGraphs.SimpleEdge}:
 Edge 1 => 3
 Edge 3 => 5

```

---

<div class="post-metadata">

**Author:** ![F\_A](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/f_a/32/53159_2.png) [@F\_A](https://discourse.julialang.org/u/F_A)\
**Post date:** [February 17, 2023, 10:28am UTC](https://discourse.julialang.org/t/graph-jl-how-to-interpret-the-output-information-returned-by-the-shortest-path-algorithms/94752/5 "2023-02-17T10:28:16Z")

</div>

> [@gdalle](#):
>
> `astar = Graphs.a_star(g, 1, 5, distmx, heuristic, edgetype_to_return)`

Hi @gdalle Many thanks for your time and Thank you very much for all the replies.

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [February 17, 2023, 10:34am UTC](https://discourse.julialang.org/t/graph-jl-how-to-interpret-the-output-information-returned-by-the-shortest-path-algorithms/94752/6 "2023-02-17T10:34:33Z")

</div>

Update: I just merged the first PR I mentioned, so the latest version of SimpleWeightedGraphs (1.3.0) should fix this.

---

<div class="post-metadata">

**Author:** ![F\_A](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/f_a/32/53159_2.png) [@F\_A](https://discourse.julialang.org/u/F_A)\
**Post date:** [February 17, 2023, 10:56am UTC](https://discourse.julialang.org/t/graph-jl-how-to-interpret-the-output-information-returned-by-the-shortest-path-algorithms/94752/7 "2023-02-17T10:56:28Z")

</div>

> [@gdalle](#):
>
> [JuliaGraphs/SimpleWeightedGraphs.jl · GitHub](https://github.com/JuliaGraphs/SimpleWeightedGraphs.jl/issues/6)) which will soon be fixed thanks to a PR by @etienne_dg ([rework of weighted graphs API, fixes #6 and Graphs#42 by etiennedeg · Pull Request #14 · JuliaGraphs/SimpleWeightedGraphs.jl · GitHub](https://github.com/JuliaGraphs/SimpleWeightedGraphs.jl/pull/14))

Hi again @gdalle Many thanks for following up on this.  
Do you this one? [JuliaGraphs/SimpleWeightedGraphs.jl · GitHub](https://github.com/JuliaGraphs/SimpleWeightedGraphs.jl/issues/6)) which will soon be fixed thanks to a PR by @etienne_dg ([rework of weighted graphs API, fixes #6 and Graphs#42 by etiennedeg · Pull Request #14 · JuliaGraphs/SimpleWeightedGraphs.jl · GitHub](https://github.com/JuliaGraphs/SimpleWeightedGraphs.jl/pull/14))

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [February 17, 2023, 10:59am UTC](https://discourse.julialang.org/t/graph-jl-how-to-interpret-the-output-information-returned-by-the-shortest-path-algorithms/94752/8 "2023-02-17T10:59:42Z")

</div>

Yes exactly that one. The second one fixing the `maxdist` behavior is still under review

---

<div class="post-metadata">

**Author:** ![F\_A](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/f_a/32/53159_2.png) [@F\_A](https://discourse.julialang.org/u/F_A)\
**Post date:** [February 17, 2023, 11:10am UTC](https://discourse.julialang.org/t/graph-jl-how-to-interpret-the-output-information-returned-by-the-shortest-path-algorithms/94752/9 "2023-02-17T11:10:36Z")

</div>

Thanks a lot @gdalle Appreciate your time

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [February 17, 2023, 11:12am UTC](https://discourse.julialang.org/t/graph-jl-how-to-interpret-the-output-information-returned-by-the-shortest-path-algorithms/94752/10 "2023-02-17T11:12:22Z")

</div>

No problem! Could you select one of my answers as the solution, so that this post shows up as resolved?

---

<div class="post-metadata">

**Author:** ![F\_A](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/f_a/32/53159_2.png) [@F\_A](https://discourse.julialang.org/u/F_A)\
**Post date:** [February 17, 2023, 11:13am UTC](https://discourse.julialang.org/t/graph-jl-how-to-interpret-the-output-information-returned-by-the-shortest-path-algorithms/94752/11 "2023-02-17T11:13:23Z")

</div>

Done. Thanks again!