# Differences in methods of constructing graph and calculating the shortest path

**URL:** <https://discourse.julialang.org/t/differences-in-methods-of-constructing-graph-and-calculating-the-shortest-path/61877>\
**Category:** Graphs\
**Tags:** question, package, performance, lightgraphs, graphs\
**Created:** [May 26, 2021, 6:19pm UTC](https://discourse.julialang.org/t/differences-in-methods-of-constructing-graph-and-calculating-the-shortest-path/61877 "2021-05-26T18:19:55Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![trathi](https://avatars.discourse-cdn.com/v4/letter/t/7c8e57/32.png) [@trathi](https://discourse.julialang.org/u/trathi)\
**Post date:** [May 26, 2021, 6:19pm UTC](https://discourse.julialang.org/t/differences-in-methods-of-constructing-graph-and-calculating-the-shortest-path/61877/1 "2021-05-26T18:19:55Z")

</div>

Hi. I am new to using `LightGraphs` and `SimpleWeightedGraph` and have a few questions regarding their usage:

1. I see that edges with zero weights are ignored when using `add_edge!` to define edges (also mentioned [here](https://github.com/JuliaGraphs/SimpleWeightedGraphs.jl)); 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?

```julia
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 

```

1. Another difference I noticed is if I don’t define the nodes continuously starting from 1,  
then constructing a graph using `add_edges!` throws an error, whereas using the second method works perfectly fine.

```julia
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 5-element Vector{Float64} at index [10]`

```julia
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?

1. 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)`, where `s` and `d` are the nodes between which I want to find the minimal path. I suspect that `dijkstra_shortest_path(g, s)` evaluates the shortest path between `s` and all other nodes, and then calling `enumerate_paths` returns the path between `s` and `d` specifically. Am I wrong? If not, can I somehow avoid the extra time spent calculating the distance between `s` and every other node, but rather directly get the path/distance between `s` and `d`—[I may be totally wrong here, any corrections and suggestions appreciated].

2. `enumerate_paths(...)` return the shortest path; however, is there a built-in function that also returns the distance (I understand that I can calculate it once I have the path, but I am just curious).

3. 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 usual `addprocs(n)` at the start of the code and then `Parallel.dijkstra_shortest_paths(g, s)`. Is this the correct way, or am I missing out on something?

Thanks!