Solving Quickest Path Problem in Networks using Python

Author: Kien Trung Nguyen & Tran Thu Le
Date: 13/02/2023

Problem definition

Let $G=(V, E, \ell, c, \sigma)$ be an undirected connected graph with vertex set $V$, edge set $E$. Each edge $e\in E$ has a length $\ell_e$ and a capacity $c_e$. $\sigma>0$ is a given amount of data. Denote by $\mathcal P(u, v)$ the set if all paths connecting $u, v\in V$. For $\rho\in \mathcal P(u, v)$, denote $\ell(\rho) = \sum_{e\in \rho}\ell_e$ the length and $c(\rho)=\min_{e\in \rho} c_e$ the capacity of $\rho$. The transmission time of $\sigma$ units of data is over a path $\rho$

$$T(\rho) := \ell(\rho) + \frac{\sigma}{c(\rho)}$$

Let $s, t\in V$ be two given vertices on the graph, called source and target, respectively. The Quickest Path (QP) problem on $G$ aims to find the path $\rho\in \mathcal P(s, t)$ that minimize the transmission time, i.e. solving the following optimization problem
$$\rho^\star \in \argmin_{\rho\in \mathcal P(s, t)} \hspace{0.5cm}T(\rho) \tag{Quickest Path}$$

Solving Idea

To solve the QP problem, we may applying the following simple idea.

Let $\{c_1, ..., c_m\}$ be the distinct capacity values of $\{c_e: e\in E\}$.

We can decompose $\mathcal P$ into $\mathcal P_i$ corresponding to $c_i$ as follows
$$\mathcal P(s, t) = \bigcup_{i=1,...,m}\mathcal P_i = \bigcup_{i=1,...,m}\{\rho\in \mathcal P(s, t): c(\rho)=c_i\}.$$
Consider the subproblem of QP w.r.t. $\mathcal P_i$, define $$\rho^\star_i \in \argmin_{\rho\in \mathcal P_i} T(\rho).$$
We then can recover $\rho^\star$ from $\rho^\star_i$ as follows
$$\rho^\star = \argmin_{i=1,...,m} T(\rho^\star_i).$$

So, we can solve the problem by finding $\rho_i^\star$. This can be done as follows.

For $\rho\in \mathcal P_i$, one observes that $\rho$ does not go through $e\in E$ if $c_e<c_i$. Let $G_i$ be the copy of $G$ by removing all edge $e\in E$ such that $c_e<c_i$. Then, it is clear that $\mathcal P_i \subset G_i$. Furthermore, the capacity of $\rho\in \mathcal P_i$ is constant. Thus, the quickest paths coincide with the shortest paths on $G_i$. We then obtain the following theorem.

Theorem. $\rho$ is a quickest path on $G_i$ iff it is a shortest path on $G_i$

So we may solve the QP problem by using the following steps:

1. Define $G_i$
2. Find $\rho_i^\star$ the shortest path on $G_i$ connecting $s, t$
3. Find $\rho^\star$ among $\rho^\star_i$ with smallest transmission time

Python code

Installation

We solve problem on network, we use networkx package. We also neeed numpy to work with array and matplotlib for drawing.
You can install these package from the terminal as follows

pip install numpy matplotlib networkx

We then import theses packages

import networkx as nx
import matplotlib.pyplot as plt
import numpy as np

Graph data structure

We may construct the graph as follows:

EDGES = [("s", "v1", {"len": 3, "cap": 4}),
         ("v1", "v3", {"len": 6, "cap": 4}),
         ("v3", "t", {"len": 6, "cap": 4}),
         ("s", "v2", {"len": 5, "cap": 5}),
         ("v2", "v4", {"len": 4, "cap": 2}),
         ("v4", "t", {"len": 8, "cap": 2}),
         ("v2", "v3", {"len": 4, "cap": 4}),
         ("v1", "v4", {"len": 3, "cap": 5})]

POSITIONS = {"s": (0, 0), "v1": (1, 1), "v2": (1, -1), "v3": (2, 1), "v4": (2, -1), "t": (3, 0)}

G = nx.Graph()
G.add_edges_from(EDGES)
cap = nx.get_edge_attributes(G, 'cap')
cap_sorted = np.sort([v for k, v in cap.items()])
cap_sorted = list(set(cap_sorted))
G.graph["cap_sorted"] = cap_sorted
G.graph["sigma"] = 20

The graph is represented by EDGES. Each edge is a tuple with three elements:

• the start node
• the end node and
• edge attributes: "len" (length) and "cap" (capacity).

The POSITIONS dictionary defines the position of each node in 2D space (x, y). The graph has two attributes: "cap_sorted" is the list of distinct capacities of all edges sorted in ascending order and 2) "sigma" an amount of transmisstion data equal to 20.

Vizualization of graph

def plot_graph(G, path=None, ax=None):
    # plt.figure(figsize=(7, 3))
    wei = nx.get_edge_attributes(G, 'len')
    cap = nx.get_edge_attributes(G, 'cap')
    labels = {}
    for k, v in wei.items():
        labels[k] = (v, cap[k])
    # pos = nx.spring_layout(G)
    nx.draw(G, pos=POSITIONS, ax=ax, with_labels=True)
    nx.draw_networkx_nodes(G, pos=POSITIONS, ax=ax,
                           node_color="cyan", alpha=0.5)
    nx.draw_networkx_edge_labels(
        G, pos=POSITIONS, ax=ax, edge_labels=labels, label_pos=0.7)
    # plt.savefig("graph.png")

    if path is not None:
        edges = [(path[i], path[i + 1]) for i in range(len(path) - 1)]
        nx.draw_networkx_edges(
            G, pos=POSITIONS, ax=ax, edgelist=edges, edge_color="red", width=10, alpha=0.3)


plt.figure(figsize=(7, 3))
plot_graph(G)
plt.show()

The graph G will look like this

Algorithm

Utilities functions:

def get_shortest_path(G):
    # return shortest path
    return nx.shortest_path(G, source="s", target="t", weight="len")

def get_length(G, path):
    # return the length of path in graph G
    length = 0
    for i in range(len(path)-1):
        a = path[i]
        b = path[i+1]
        len_ab = G.edges[a, b]["len"]
        length += len_ab
    return length

def get_time(G, path, capacity):
    # return the tranmission time
    time  = get_length(G, path) + G.graph["sigma"]/capacity
    return time  

def get_removed_edges(G, capacity):
    removed_edges = []
    for e in G.edges:
        ce = G.edges[e]["cap"] 
        if ce < capacity:
            removed_edges += [e]
    return removed_edges

def new_graph(G, removed_edges=None):
    Gnew = G.copy()
    if removed_edges is not None:
        Gnew.remove_edges_from(removed_edges)
    return Gnew   

Here we define some utilities functions:

1. get_shortest_path(G) returns the shortest path in the graph G from the source node “s” to the target node “t”.

2. get_length(G, path) takes a graph G and a path as input and returns the total length of the path.

3. get_time(G, path, capacity) takes a graph G, a path, and a capacity as input and returns the transmission time of that path.

4. get_removed_edges(G, capacity) takes a graph G and a capacity as input and returns a list of edges that have a capacity less than the specified capacity.

5. new_graph(G, removed_edges=None) creates a new copy of the original graph G by removing all edges in the list removed_edges.

Function for finding quickest path:
We now move to the main algorithm finding the quickest path.

def find_quickest_path(G):
    data = {"shortest_path": [], 
            "length_shortest_path": [], 
            "time": [],
            "removed_edges": [],
            "index_of_quickest_path": None,
            "quickest_path": None}
    cap_sorted = G.graph["cap_sorted"]
    for cap in cap_sorted:
        removed_edges = get_removed_edges(G, capacity=cap)
        Gnew = new_graph(G, removed_edges=removed_edges)
        try:
            shortest_path = get_shortest_path(Gnew)
            length_shortest_path = get_length(G, path=shortest_path)
            time = length_shortest_path + G.graph["sigma"]/cap
        except:
            shortest_path = None
            length_shortest_path = "infinity"
            time = "infinity"

        data["shortest_path"] += [shortest_path]
        data["length_shortest_path"] += [length_shortest_path]
        data["time"] += [time]
        data["removed_edges"] += [removed_edges]

    # find the quickest path
    id_min = np.argmin(np.array(data["time"][:-1]))
    data["index_of_quickest_path"] = id_min   
    data["quickest_path"] = data["shortest_path"][id_min]    

    return data

This code defines a function find_quickest_path(G) that finds the quickest path in a given graph G.

The function first creates a dictionary data to store information about the shortest paths. The keys of the dictionary include:

• shortest_path: a list of the shortest paths for each capacity.
• length_shortest_path: a list of the lengths of the shortest paths for each capacity.
• time: a list of the transmission times for each capacity.
• removed_edges: a list of the edges that have been removed for each capacity.
• index_of_quickest_path: the index of the quickest path in the data
• quickest_path: the quickest path.

Showing results:

We can add code for vizualization purpose.

def viz_quickest_path(quickest_data):
    list_removed_edges = quickest_data["removed_edges"]
    n = len(list_removed_edges)

    fig, axs = plt.subplots(3, 1, figsize=(7, 3*n))
    for i in range(n):
        Gnew = G.copy()
        Gnew.remove_edges_from(list_removed_edges[i])
        shortest_path = quickest_data["shortest_path"][i]
        time = quickest_data["time"][i]

        ax = axs[i]
        plot_graph(Gnew, shortest_path, ax=ax)
        ax.set_title(
            f'Iter i={i}, ci={Gnew.graph["cap_sorted"][i]}, Qi={time}')

    str_path = "[" + " ".join(quickest_data["quickest_path"]) + "]"
    fig.suptitle(
        f"Iterations of Finding Quickest Path\nThe Quickest Path here is {str_path}")


quickest_data = find_quickest_path(G)
viz_quickest_path(quickest_data)

Here is the result.