Question: You are given a directed graph with node set = {0, 1, ... , 1}, and arc set = {(, ): there exists a directed

You are given a directed graph with node set = {0, 1, ... , 1}, and arc set = {(, ): there exists a directed edge }. Each edge (, ) is associated with a length ,. Formulate the problem of finding the shortest path from node 0 to node 1 as a linear program.

Using Python, write a program to formulate and solve the above optimization problem using Gurobi. Your program should read in the graph from the provided data file:

origin destination length
0 3 3
11 0 3
0 19 1
37 0 5
0 39 4
53 0 2
0 61 9
98 0 8
1 2 5
38 1 7
2 25 8
26 2 3
3 9 6
17 3 5
3 85 9
99 3 8
4 94 2
98 4 8

hw3_graph.csv contains a data frame with three columns. Each row represents an edge of the graph, going from node origin to node destination and having length length Report the shortest path in human-readable format (e.g. 0 2 5 ... N-1), as well as the shortest-path length. Hint: you may find it useful to represent the graph using the NetworkX package in Python, but it is not required.

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related General Management Questions!