# Solving the Shortest Path Problem with GUROBI
# 1. Import Libraries
The first step is importing the libraries.


```python
import csv
import networkx as nx
import matplotlib.pyplot as plt
from gurobipy import *  # GRB_INIT
```

# 2. Given Data
## 2.1 Getting Link List and Link Costs


```python
links = tuplelist()
cost = {}
with open("links_shortest_path.csv", 'r') as csv_file:
    csv_reader = csv.reader(csv_file, delimiter=',', quotechar='|', quoting=csv.QUOTE_MINIMAL)
    for row in csv_reader:
        if csv_reader.line_num > 1:
            from_node = int(row[0])
            end_node = int(row[1])
            cost[from_node, end_node] = float(row[2])
            links.append((from_node, end_node))
print(cost)
```

    {(0, 11): 30.0, (0, 12): 10.0, (0, 13): 20.0, (11, 12): 5.0, (11, 14): 20.0, (11, 15): 30.0, (12, 13): 50.0, (12, 14): 30.0, (12, 15): 30.0, (13, 14): 30.0, (13, 15): 20.0, (14, 20): 30.0, (15, 20): 30.0}


## 2.2 Nodes


```python
nodes = [x[0] for x in links] + [x[1] for x in links]
nodes = set(nodes)
nodes = list(nodes)
source_node = 0
destination_node = 20

```

# 3. Creating Model Object 


```python
m = Model()  # GRB_INIT
```

# 3. Defining Decision Variables


```python
decision_l = m.addVars(links, vtype=GRB.BINARY)

```

# 4. Objective Function
\begin{equation}
\label{eq:obj}
\sum\limits_{(u,v)\in\mathcal{E}} l_{(u,v)} * cost_{(u,v)}
\end{equation}


```python
m.setObjective(quicksum(decision_l[u, v] * cost[u, v] for u, v in links), GRB.MINIMIZE)
```

# 5. Constraints
\begin{equation}
\label{eq:routing}
\sum\limits_{v\in\mathcal{V}} l_{(u,v)} - \sum\limits_{v\in\mathcal{V}} l_{(v,u)}  =
\begin{cases} 
1, & \text{if } u = source\_node \\
-1,& \text{if } u = destination\_node \\
0, & \text{otherwise}
\end{cases}
\\ \forall u\in\mathcal{V}
\end{equation}


```python
for u in nodes:
    m.addConstr(quicksum(decision_l[u, v] for u, v in links.select(u, '*'))
                - quicksum(decision_l[v, u] for v, u in links.select('*', u)) ==
                (1 if u == source_node else -1 if u == destination_node else 0))
```

# 6. Running Solver


```python
m.optimize()
```

    Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)
    Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
    Optimize a model with 7 rows, 13 columns and 26 nonzeros
    Model fingerprint: 0xf2e9cbcf
    Variable types: 0 continuous, 13 integer (13 binary)
    Coefficient statistics:
      Matrix range     [1e+00, 1e+00]
      Objective range  [5e+00, 5e+01]
      Bounds range     [1e+00, 1e+00]
      RHS range        [1e+00, 1e+00]
    Found heuristic solution: objective 80.0000000
    Presolve removed 7 rows and 13 columns
    Presolve time: 0.10s
    Presolve: All rows and columns removed
    
    Explored 0 nodes (0 simplex iterations) in 0.56 seconds
    Thread count was 1 (of 8 available processors)
    
    Solution count 2: 70 
    
    Optimal solution found (tolerance 1.00e-04)
    Best objective 7.000000000000e+01, best bound 7.000000000000e+01, gap 0.0000%


# 7. Selected Links


```python
for u, v in links:
    if decision_l[u, v].x == 1:
        print("u:{} v:{} l:{}".format(u,v,decision_l[u, v].x * cost[u, v]))
```

    u:0 v:12 l:10.0
    u:12 v:15 l:30.0
    u:15 v:20 l:30.0


# 8. Plot Results


```python
G = nx.DiGraph()
G.add_nodes_from(nodes)
for u, v in links:
    G.add_edge(u, v)

# Adding the position attribute to each node
node_pos = {0: (0, 4),
            11: (2, 2), 12: (2, 4), 13: (2, 6), 14: (4, 3), 15: (4, 6),
            20: (6, 4)}

# Create a list of edges in shortest path
red_edges = [(i, j) for i, j in links if decision_l[i, j].x > 0]

# Create a list of nodes in shortest path
sp = [i for i, j in links if decision_l[i, j].x > 0]
sp.append(destination_node)

# If the node is in the shortest path, set it to red, else set it to white color
node_col = ['white' if not node in sp else 'red' for node in G.nodes()]
# If the edge is in the shortest path set it to red, else set it to white color
edge_col = ['black' if not edge in red_edges else 'red' for edge in G.edges()]
# Draw the nodes
nx.draw_networkx(G, node_pos, node_color=node_col, node_size=450)
# Draw the node labels
# nx.draw_networkx_labels(G1, node_pos,node_color= node_col)
# Draw the edges
nx.draw_networkx_edges(G, node_pos,edge_color=edge_col)
# Draw the edge labels
nx.draw_networkx_edge_labels(G, node_pos, edge_color=edge_col, edge_labels=cost)
# Remove the axis
plt.axis('off')

# Show the plot
plt.show()

```


```python

```


```python

```


```python

```


```python

```


```python

```

ad4b42c45cc759be3bff2dac1e0c849ceda9c49d
ipynb
Jupyter Notebook
notebooks/.ipynb_checkpoints/shortest_path-checkpoint.ipynb
TurgayPamuklu/GreenRAN
9fb61ba709ab171e0d85def1b89caa72a9cfe312
MIT
notebooks/.ipynb_checkpoints/shortest_path-checkpoint.ipynb
TurgayPamuklu/GreenRAN
9fb61ba709ab171e0d85def1b89caa72a9cfe312
MIT
notebooks/.ipynb_checkpoints/shortest_path-checkpoint.ipynb
TurgayPamuklu/GreenRAN
9fb61ba709ab171e0d85def1b89caa72a9cfe312
MIT
Qwen/Qwen-72B
1. YES
2. YES