HLPL / VerTeX Modelling Language Documentation

← examples

# Shortest Path Problem
# Finds the shortest path from node 1 to node 4 in a directed network
# Demonstrates flow conservation constraints and use of setminus operator

model shortest_path
set N = {1, 2, 3, 4}                                            # Nodes in the network

const d = {{0, 2, infty, 11},
           {2, 0, 3, 8},
           {6, 3, 0, 4},
           {11, 8, 4, 0}}, forall i in N, forall j in N        # Distance from node i to node j

bin x, forall i in N, forall j in N                            # 1 if arc (i,j) is in the path

# Objective: Minimize total path distance
min sum_{i in N}{sum_{j in N setminus {i}}{d_{i,j} * x_{i,j}}}

# Flow conservation at source node (node 1): net outflow = 1
constr sum_{j in N setminus {1}}{x_{1,j}} - sum_{j in N setminus {1}}{x_{j,1}} = 1

# Flow conservation at intermediate nodes: net outflow = 0
constr sum_{j in N setminus {i}}{x_{i,j}} - sum_{j in N setminus {i}}{x_{j,i}} = 0, forall i in N setminus {1, 4}

# Flow conservation at sink node (node 4): net outflow = -1
constr sum_{j in N setminus {4}}{x_{4,j}} - sum_{j in N setminus {4}}{x_{j,4}} = -1
end

import elytica
import json

# The model's distance matrix, to print each edge's length. None is `infty`.
DIST = [[0, 2, None, 11],
        [2, 0, 3, 8],
        [6, 3, 0, 4],
        [11, 8, 4, 0]]

def main():
    elytica.init_model("shortest_path")
    elytica.run_model("shortest_path")

    N = elytica.get_model_set("shortest_path", "N")

    # Collect solution
    path_edges = []
    total_distance = 0

    print("\n" + "="*60)
    print("SHORTEST PATH SOLUTION")
    print("="*60)
    print("\nPath (node -> node):")
    print("-"*60)

    for i in N:
        for j in N:
            val = elytica.get_variable_value("shortest_path", f"x{i},{j}")
            if val > 0.5:
                dist = DIST[i - 1][j - 1]
                path_edges.append({"from": i, "to": j, "distance": dist})
                print(f"  {i} -> {j}  (distance: {dist})")

    # Get objective value (total distance)
    obj_value = elytica.get_best_primal_bound("shortest_path")

    print("-"*60)
    print(f"Total Distance: {obj_value:.2f}")
    print("="*60)

    # Construct ordered path from node 1 to node 4
    ordered_path = [1]
    current = 1
    while current != 4:
        for edge in path_edges:
            if edge["from"] == current:
                ordered_path.append(edge["to"])
                current = edge["to"]
                break

    print(f"\nOrdered Path: {' -> '.join(map(str, ordered_path))}")
    print("="*60)

    # Prepare results for output
    results = {
        "objective_value": obj_value,
        "path_edges": path_edges,
        "ordered_path": ordered_path
    }

    elytica.write_results(json.dumps(results, indent=2))

    return 0

Read this through MCP: read with path: "examples/shortest-path", or resource hlpl://examples/shortest-path.