Shortest paths

In network analysis, finding the shortest path between two nodes is often done using algorithms like Dijkstra’s, Bellman-Ford, Floyd-Warshall, A-star, etc. However, these methods are particularly designed for the specific case of finding shortest paths and cannot be easily adapted for other tasks. Also, they have particular assumptions, for example, Dijkstra doesn’t work with negative weights, and Bellman-Ford doesn’t work with negative cycles.

CORNETO isn’t just another library for shortest paths. Instead, CORNETO allows you to model shortest-path problems using constrained optimization. This means that you have a flexible framework to formulate and solve these problems, making CORNETO a versatile tool. By converting a graph into a network flow problem, CORNETO can easily handle shortest path problems that are solved by any LP and ILP solver, or you can use this problem to build more advanced ones.

Note

Please note that formulating the shortest path as an LP problem isn’t always the best approach. LP solvers might be slower than dedicated algorithms like Dijkstra’s or Bellman-Ford for simpler cases, especially when there’s no need for the added flexibility of LP.

In this tutorial, we will see how to use CORNETO to solve shortest-path problems and find a solution using an LP solver.

Creating a weighted graph

import numpy as np

import corneto as cn

cn.info()

Installed version: v1.0.0a0 (latest: v1.0.0-alpha) Available backends: CVXPY v1.5.3, PICOS v2.4.17 Default backend (corneto.opt): CVXPY Installed solvers: CLARABEL, CVXOPT, ECOS, ECOS_BB, GLPK, GLPK_MI, OSQP, SCIP, SCIPY, SCS Graphviz version: v0.20.3 Repository: https://github.com/saezlab/corneto

G = cn.Graph()
G.add_edge("A", "B", weight=1)
G.add_edge("A", "C", weight=1)
G.add_edge("B", "D", weight=1)
G.add_edge("C", "E", weight=1)
G.add_edge("E", "F", weight=1)
G.add_edge("D", "F", weight=1)
G.add_edge("F", "G", weight=1)
G.plot()

from corneto.methods import solve_shortest_path

# TODO: a graph problem should have the graph attached to it...
edges, P, Gc = solve_shortest_path(G, "A", "G", solver="SCIPY")
Gc.edge_subgraph(edges).plot(orphan_edges=False)

P.objectives[0].value

4.0

Random graphs

# Create a function that generates a shortest path problem on a random graph created with networkx
import networkx as nx


def create_random_graph(n, m=3, seed=None, directed=True):
    G = nx.barabasi_albert_graph(n, m, seed=seed)
    vertices = list(G.nodes())
    # Add random weights to the edges
    for u, v in G.edges():
        G[u][v]["weight"] = np.random.uniform(1, 10)  # np.random.randint(1, 20)
    s, t = np.random.choice(vertices, 2, replace=False)
    if directed:
        G = G.to_directed()
    return G, s, t


G, s, t = create_random_graph(5000)

nx.shortest_path(G, s, t, weight="weight")

[524, 790, 783, 2035, 2215, 273]

nx.shortest_path_length(G, s, t, weight="weight")

14.645733467514843

Gc = cn.Graph.from_networkx(G)

sol, Ps, Gcs = solve_shortest_path(Gc, s, t, solver="SCIPY")
Ps.objectives[0].value

14.645733467514843

Gcs.edge_subgraph(sol).plot(orphan_edges=True)