Hi. I am new to using LightGraphs
and SimpleWeightedGraph
and have a few questions regarding their usage:
 I see that edges with zero weights are ignored when using
add_edge!
to define edges (also mentioned here); however, if I define the graph using sources, destination, and weights vector, it seems to account for zero weight edges correctly (see below). So, can I safely use the second way of defining a graph if I have zero weight edges os is there a catch?
using LightGraphs, SimpleWeightedGraphs
g = SimpleWeightedGraph(5)
add_edge!(g, 1, 2, 0.5)
add_edge!(g, 1, 4, 0.5)
add_edge!(g, 1, 5, 1)
add_edge!(g, 2, 3, 0.5)
add_edge!(g, 2, 4, 0.2)
add_edge!(g, 3, 4, 0) #Throws warning: adding edges with a zero weight to this graph type has no effect.
add_edge!(g, 4, 5, 0)
print(enumerate_paths(dijkstra_shortest_paths(g, 1), 5))
# Output: [1, 5] > This is incorrect
#Defining the same graph in a different way
sources = [1,1,1,2,2,3,4]
destinations = [2,4,5,3,4,4,5]
weights = [0.5, 0.5, 1, 0.5, 0.2, 0, 0]
g = SimpleWeightedGraph(sources, destinations, weights)
print(enumerate_paths(dijkstra_shortest_paths(g, 1), 5))
# Output: [1, 4, 5] > This is correct
 Another difference I noticed is if I don’t define the nodes continuously starting from 1,
then constructing a graph usingadd_edges!
throws an error, whereas using the second method works perfectly fine.
using LightGraphs, SimpleWeightedGraphs
# Here the nodes are represented as '10, 20, 30, 40, and 50 (previously there were 1,2,3,4,5)'
g = SimpleWeightedGraph(5)
add_edge!(g, 10, 20, 0.5)
add_edge!(g, 10, 40, 0.5)
add_edge!(g, 10, 50, 1)
add_edge!(g, 20, 30, 0.5)
add_edge!(g, 20, 40, 0.2)
add_edge!(g, 30, 40, 0)
add_edge!(g, 40, 50, 0)
print(enumerate_paths(dijkstra_shortest_paths(g, 10), 50))
ERROR: LoadError: BoundsError: attempt to access 5element Vector{Float64} at index [10]
using LightGraphs, SimpleWeightedGraphs
# Defining graph using this method works fine even with discontinuous nodes!
sources = [10,10,10,20,20,30,40]
destinations = [20,40,50,30,40,40,50]
weights = [0.5, 0.5, 1, 0.5, 0.2, 0, 0]
g = SimpleWeightedGraph(sources, destinations, weights)
print(enumerate_paths(dijkstra_shortest_paths(g, 10), 50))
# Output: [10, 40, 50] > This is correct
Is this expected behavior, or should I not define zero weight edges and discontinuous nodes even with the second method of constructing a graph?
Considering the above two points, why would one want to use add_edge!
instead of the second method, which clearly is more generic?

If I am trying to simply find the shortest distance between two nodes in a large graph (say 1000 nodes and 100,000 edges), then what is the most efficient way of doing so? Currently, I execute
enumerate_paths(dijkstra_shortest_paths(g, s), d)
, wheres
andd
are the nodes between which I want to find the minimal path. I suspect thatdijkstra_shortest_path(g, s)
evaluates the shortest path betweens
and all other nodes, and then callingenumerate_paths
returns the path betweens
andd
specifically. Am I wrong? If not, can I somehow avoid the extra time spent calculating the distance betweens
and every other node, but rather directly get the path/distance betweens
andd
—[I may be totally wrong here, any corrections and suggestions appreciated]. 
enumerate_paths(...)
return the shortest path; however, is there a builtin function that also returns the distance (I understand that I can calculate it once I have the path, but I am just curious). 
Lastly, I don’t see any major difference in the execution time when I use
LightGraphs.Parallel
for large graphs (~1000 nodes, ~100,000 nodes). I do the usualaddprocs(n)
at the start of the code and thenParallel.dijkstra_shortest_paths(g, s)
. Is this the correct way, or am I missing out on something?
Thanks!