Shortest Paths

In this exercise, we will use shortest path functions. You are given a directed graph as an adjacency matrix stored in '3directedgraph.csv'. The value of an entry in the $i$-th row and $j$-th column in the matrix corresponds to the length attribute of edge $(i,j)$. Your first task is to read this file and store the graph as a Networkx DiGraph. Note that the nodes must be labelled $1$ through $20$.

In [1]:
import numpy as np
import csv
import networkx as nx

#---------- Your code here ------------#

#--------------------------------------#

We will now use some of the shortest path algorithms in Networkx to compute the following.

Q1. What is the length of a shortest path from node $1$ to node $18$? Also, what is the path?

In [2]:
#---------- Your code here ------------#

#--------------------------------------#

5
[1, 20, 9, 18]

Q2. What is the length of a shortest path from node $1$ to node $18$, that does pass through node $19$? Also, what is the path? (you can travel the same edge twice if you need to)

In [3]:
#---------- Your code here ------------#

#--------------------------------------#

8
[1, 20, 19, 18]

Q3. What is the length of a shortest path from node $1$ to node $18$, that does not pass through node $9$? Also, what is the path?

In [4]:
#---------- Your code here ------------#

#--------------------------------------#

7
[1, 20, 12, 18]

Q4. What is the length of a shortest path from node $1$ to node $18$, that does pass through edge $(5,6)$? Also, what is the path?

In [5]:
#---------- Your code here ------------#

#--------------------------------------#

16
[1, 20, 5, 6, 7, 18]
In [ ]: