# Comparing Dijkstra and Bellman Ford Shortest Paths Algorithms using PyDataStructs¶

## Dataset¶

We have used California road network from Stanford Network Analysis Project. The intent of this demo is to show how **pydatastructs** can be used for research and analysis purposes.

The above dataset is a road network of California as the name suggests. The intersections and endpoints in this network are represented as vertices and the roads between them are represented as undirected edges. The data is read from a `txt`

file where each line contains two numbers representing two points of an edge in the graph. We have used varying number of these edges to analyse how each algorithm responds to the varying scale of the shortest path problem at hand.

## Results¶

We observed that for low inverse density (total number of possible edges divided by number of edges present) graphs, both algorithms take similar amounts of time. However Dijkstra algorithm performs significantly better with high inverse density graphs as compared to Bellman Ford algorithm.

```
# Import modules and APIs for Graphs
from pydatastructs import Graph, AdjacencyListGraphNode
from pydatastructs import shortest_paths, topological_sort
# Import utility modules
import timeit, random, functools, matplotlib.pyplot as plt
```

```
def create_Graph(num_edges, file_path, ignore_lines=4):
"""
Creates pydatastructs.Graph object.
Parameters
==========
num_edges: int
Number of edges that should be present in the
pydatastructs.Graph object.
file_path: str
The path to the file containing California
road network dataset.
ignore_lines: int
Number of inital lines that should be ignored.
Optional, by default 4 because the first 4 lines
contain documentation of the dataset which is not
required to generate the pydatastructs.Graph object.
Returns
=======
G: pydatastructs.Graph
"""
f = open(file_path, 'r')
for _ in range(ignore_lines):
f.readline()
G = Graph()
inp = f.readline().split()
for _ in range(num_edges):
u, v = inp
G.add_vertex(AdjacencyListGraphNode(u))
G.add_vertex(AdjacencyListGraphNode(v))
G.add_edge(u, v, random.randint(1, 1000))
inp = f.readline().split()
return G
```

```
def generate_data(file_name, min_num_edges, max_num_edges, increment):
"""
Generates computation time data for Dijkstra and Bellman ford
algorithms using pydatastructs.shortest_paths.
Parameters
==========
file_path: str
The path to the file containing California
road network dataset.
min_num_edges: int
The minimum number of edges to be used for
comparison of algorithms.
max_num_edges: int
The maximum number of edges to be used for comparison
of algorithms.
increment: int
The value to be used to increment the scale of the
shortest path problem. For example if using 50 edges,
and increment value is 10, then in the next iteration,
60 edges will be used and in the next to next iteration,
70 edges will be used and so on until we hit the max_num_edges
value.
Returns
=======
graph_data, data_dijkstra, data_bellman_ford: (list, list, list)
graph_data contains tuples of number of vertices and number
of edges.
data_dijkstra contains the computation time values for each
graph when Dijkstra algorithm is used.
data_bellman_ford contains the computation time values for each
graph when Bellman ford algorithm is used.
"""
data_dijkstra, data_bellman_ford, graph_data = [], [], []
for edge in range(min_num_edges, max_num_edges + 1, increment):
G = create_Graph(edge, file_name)
t = timeit.Timer(functools.partial(shortest_paths, G, 'dijkstra', '1'))
t_djk = t.repeat(1, 1)
t = timeit.Timer(functools.partial(shortest_paths, G, 'bellman_ford', '1'))
t_bf = t.repeat(1, 1)
graph_data.append((len(G.vertices), len(G.edge_weights)))
data_dijkstra.append(t_djk[0])
data_bellman_ford.append(t_bf[0])
return graph_data, data_dijkstra, data_bellman_ford
```

```
def plot_data(graph_data, data_dijkstra, data_bellman_ford):
"""
Utility function to plot the computation time values
for Dijkstra and Bellman ford algorithms versus
the inverse density of the input graph.
"""
idensity, time_dijkstra, time_bellman_ford = [], [], []
for datum_graph, datum_djk, datum_bf in zip(graph_data, data_dijkstra, data_bellman_ford):
num_edges, num_vertices = datum_graph[1], datum_graph[0]
idensity.append((num_vertices*(num_vertices - 1))/(2*num_edges))
time_dijkstra.append(datum_djk)
time_bellman_ford.append(datum_bf)
plt.xlabel("Inverse Density of Input Graph")
plt.ylabel("Computation Time (s)")
plt.plot(idensity, time_dijkstra, label="Dijkstra")
plt.plot(idensity, time_bellman_ford, label="Bellman Ford")
plt.legend(loc="best")
plt.show()
```

```
graph_data, data_djk, data_bf = generate_data('roadNet-CA.txt', 50, 2000, 50)
```

```
plot_data(graph_data, data_djk, data_bf)
```