Dijkstra state?


#1

Hi, this is an easy task. I was wondering, what is the parameters of the dijkstra state in the following link:

struct DijkstraState{T <: Real,U <: Integer} <: AbstractPathState
    parents::Vector{U}
    dists::Vector{T}
    predecessors::Vector{Vector{U}}
    pathcounts::Vector{UInt64}
    closest_vertices::Vector{U}
end

I need to finish a task very quickly, otherwise, I would figure it out by myself. Would rally appreciate if anyone can help me.


#2

If I read the code correctly the meanings are as follows:

  • parents[v] : The vertex that comes right before v on a shortest path from the source to v.
  • dists[v]: The length of the shortest path from the source vertices to v.
  • preds[v]: The vertex that comes right before v on some shortest path from the source to v. The difference to parents is, that parents considers only one shortest path, but there could also be multiple. Is only created when allpaths is true.
  • pathcounts[v]: The number of shortest paths from the sources to v.
  • closest_vertices: A list of all the vertices of g in order of shortest distance to the sources. Is only created when trackvertices is true.