Shortest Path

Overview

Shortest-path analysis studies how to move through a graph from one node to another with the smallest possible total cost, distance, or time. In graph theory, these problems are foundational for routing, logistics, infrastructure design, and dependency analysis across connected systems. The broader mathematical setting is the Shortest path problem, where edge weights represent real-world quantities such as latency, travel time, or risk. In practical analytics workflows, shortest-path methods turn raw edge lists into interpretable decision outputs like optimal routes and path lengths.

The category combines two closely related optimization ideas: minimum path cost between selected endpoints and minimum total connection cost across all nodes. For endpoint routing, the objective is typically \min_{P\in\mathcal{P}(s,t)}\sum_{(u,v)\in P} w(u,v), where \mathcal{P}(s,t) is the set of candidate paths from source s to target t. For network-wide backbone design, the objective is to find a spanning tree T minimizing \sum_{(u,v)\in T} w(u,v) while avoiding cycles. Together, these formulations capture both point-to-point optimization and full-network efficiency.

Implementation in this category is built on NetworkX, a widely used Python library for graph creation, traversal, and algorithmic analysis. NetworkX provides robust shortest-path and tree algorithms for weighted and unweighted graphs, directed and undirected structures, and irregular node labels. The functions here wrap those algorithms in spreadsheet-friendly inputs and typed outputs so graph computations can be used directly in Excel-style models.

SHORTEST_PATH computes the route and total length between a specified source and target. It supports both unweighted edges (hop count) and weighted edges (cost-aware routing), and can treat the graph as directed when edge direction matters. This makes it useful for transport routing, workflow dependency resolution, and communication-network diagnostics where users need both the scalar optimum and the explicit node sequence. Because it returns both a length value and a path property, it supports downstream reporting, validation, and what-if sensitivity checks.

MIN_SPANNING_TREE solves a complementary problem: connect all reachable nodes with the least aggregate edge weight and no cycles. Instead of optimizing a single origin-destination route, it optimizes global connectivity, making it appropriate for cable layout, utility network planning, and cluster backbone extraction in exploratory analysis. The function returns both total tree weight and the selected edge set, which helps users audit why the total cost is minimal. Used together, SHORTEST_PATH and MIN_SPANNING_TREE provide a concise toolkit for local routing decisions and global network design trade-offs.

MIN_SPANNING_TREE

A minimum spanning tree (MST) is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.

This is a classic optimization problem with applications in designing networks (e.g., telecommunications, transportation, water supply) where you want to connect all points with the minimum total length of cable or pipe.

The function returns an Excel Data Type where the primary value is the total weight of the MST. The set of edges included in the MST is available as an ‘Edges’ property.

Excel Usage

=MIN_SPANNING_TREE(edges)

• edges (list[list], required): 2D array of edges [source, target, weight].

Returns (dict): Data type containing the total MST weight (basicValue) and the list of edges.

Example 1: Simple MST

Inputs:

edges
A	B	1
B	C	2
A	C	3

Excel formula:

=MIN_SPANNING_TREE({"A","B",1;"B","C",2;"A","C",3})

Expected output:

{"type":"Double","basicValue":3,"properties":{"Total Weight":{"type":"Double","basicValue":3},"Edges":{"type":"Array","elements":[[{"type":"String","basicValue":"A"},{"type":"String","basicValue":"B"},{"type":"Double","basicValue":1}],[{"type":"String","basicValue":"B"},{"type":"String","basicValue":"C"},{"type":"Double","basicValue":2}]]}}}

Example 2: Multiple paths MST

Inputs:

edges
A	B	10
B	C	1
A	C	5
C	D	1

Excel formula:

=MIN_SPANNING_TREE({"A","B",10;"B","C",1;"A","C",5;"C","D",1})

Expected output:

{"type":"Double","basicValue":7,"properties":{"Total Weight":{"type":"Double","basicValue":7},"Edges":{"type":"Array","elements":[[{"type":"String","basicValue":"A"},{"type":"String","basicValue":"C"},{"type":"Double","basicValue":5}],[{"type":"String","basicValue":"B"},{"type":"String","basicValue":"C"},{"type":"Double","basicValue":1}],[{"type":"String","basicValue":"C"},{"type":"String","basicValue":"D"},{"type":"Double","basicValue":1}]]}}}

Example 3: Disconnected graph (Spanning Forest)

Inputs:

edges
A	B	1
C	D	1

Excel formula:

=MIN_SPANNING_TREE({"A","B",1;"C","D",1})

Expected output:

{"type":"Double","basicValue":2,"properties":{"Total Weight":{"type":"Double","basicValue":2},"Edges":{"type":"Array","elements":[[{"type":"String","basicValue":"A"},{"type":"String","basicValue":"B"},{"type":"Double","basicValue":1}],[{"type":"String","basicValue":"C"},{"type":"String","basicValue":"D"},{"type":"Double","basicValue":1}]]}}}

Example 4: Numeric IDs MST

Inputs:

edges
1	2	100
2	3	50
1	3	10

Excel formula:

=MIN_SPANNING_TREE({1,2,100;2,3,50;1,3,10})

Expected output:

{"type":"Double","basicValue":60,"properties":{"Total Weight":{"type":"Double","basicValue":60},"Edges":{"type":"Array","elements":[[{"type":"String","basicValue":"1"},{"type":"String","basicValue":"3"},{"type":"Double","basicValue":10}],[{"type":"String","basicValue":"2"},{"type":"String","basicValue":"3"},{"type":"Double","basicValue":50}]]}}}

Python Code

Show Code

import networkx as nx

def min_spanning_tree(edges):
    """
    Find the minimum spanning tree (MST) of an undirected graph.

    See: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.tree.mst.minimum_spanning_tree.html

    This example function is provided as-is without any representation of accuracy.

    Args:
        edges (list[list]): 2D array of edges [source, target, weight].

    Returns:
        dict: Data type containing the total MST weight (basicValue) and the list of edges.
    """
    try:
        def to2d(x):
            return [[x]] if not isinstance(x, list) else x

        edges = to2d(edges)

        if not isinstance(edges, list) or not edges:
            return "Error: edges must be a non-empty 2D list"

        G = nx.Graph()
        # Ensure all rows have at least 3 elements for weighted MST
        # If weight is missing, default to 1.0
        processed_edges = []
        for row in edges:
            if len(row) >= 2:
                u, v = str(row[0]), str(row[1])
                w = float(row[2]) if len(row) >= 3 else 1.0
                processed_edges.append((u, v, w))

        if not processed_edges:
            return "Error: No valid edges found in input"

        G.add_weighted_edges_from(processed_edges)

        # networkx.minimum_spanning_tree returns a Graph object
        T = nx.minimum_spanning_tree(G, weight='weight')

        total_weight = T.size(weight='weight')

        mst_edges = []
        for u, v, d in T.edges(data=True):
            weight = d.get('weight', 1.0)
            mst_edges.append([
                {"type": "String", "basicValue": str(u)},
                {"type": "String", "basicValue": str(v)},
                {"type": "Double", "basicValue": float(weight)}
            ])

        return {
            "type": "Double",
            "basicValue": float(total_weight),
            "properties": {
                "Total Weight": { "type": "Double", "basicValue": float(total_weight) },
                "Edges": {
                    "type": "Array",
                    "elements": mst_edges
                }
            }
        }
    except Exception as e:
        return f"Error: {str(e)}"

Online Calculator

edges *

2D array of edges [source, target, weight].

---

SHORTEST_PATH

Shortest path algorithms find a path between two nodes in a graph such that the sum of the weights of its constituent edges is minimized. This is a fundamental problem in network routing, logistics, and pathfinding.

This function uses Dijkstra’s algorithm (by default) to compute the shortest path. It handles both unweighted graphs (where every edge has weight 1) and weighted graphs.

The function returns an Excel Data Type where the primary value is the shortest path length. The full sequence of nodes in the path is available as a ‘Path’ property.

Excel Usage

=SHORTEST_PATH(edges, source, target, directed)

• edges (list[list], required): 2D array of edges. Each row should be [source, target] or [source, target, weight].
• source (str, required): The starting node ID.
• target (str, required): The ending node ID.
• directed (bool, optional, default: false): If True, treat the graph as directed.

Returns (dict): Data type containing the shortest path length (basicValue) and the path node sequence.

Example 1: Unweighted undirected path

Inputs:

edges		source	target
A	B	A	D
B	C
A	C
C	D

Excel formula:

=SHORTEST_PATH({"A","B";"B","C";"A","C";"C","D"}, "A", "D")

Expected output:

{"type":"Double","basicValue":2,"properties":{"Length":{"type":"Double","basicValue":2},"Path":{"type":"Array","elements":[[{"type":"String","basicValue":"A"}],[{"type":"String","basicValue":"C"}],[{"type":"String","basicValue":"D"}]]}}}

Example 2: Weighted undirected path

Inputs:

edges			source	target
A	B	10	A	D
B	C	10
A	C	5
C	D	5

Excel formula:

=SHORTEST_PATH({"A","B",10;"B","C",10;"A","C",5;"C","D",5}, "A", "D")

Expected output:

{"type":"Double","basicValue":10,"properties":{"Length":{"type":"Double","basicValue":10},"Path":{"type":"Array","elements":[[{"type":"String","basicValue":"A"}],[{"type":"String","basicValue":"C"}],[{"type":"String","basicValue":"D"}]]}}}

Example 3: Directed path (one-way)

Inputs:

edges			source	target	directed
A	B	1	A	C	true
B	C	1

Excel formula:

=SHORTEST_PATH({"A","B",1;"B","C",1}, "A", "C", TRUE)

Expected output:

{"type":"Double","basicValue":2,"properties":{"Length":{"type":"Double","basicValue":2},"Path":{"type":"Array","elements":[[{"type":"String","basicValue":"A"}],[{"type":"String","basicValue":"B"}],[{"type":"String","basicValue":"C"}]]}}}

Example 4: Numeric node IDs

Inputs:

edges			source	target
1	2	5	1	3
2	3	5

Excel formula:

=SHORTEST_PATH({1,2,5;2,3,5}, 1, 3)

Expected output:

{"type":"Double","basicValue":10,"properties":{"Length":{"type":"Double","basicValue":10},"Path":{"type":"Array","elements":[[{"type":"String","basicValue":"1"}],[{"type":"String","basicValue":"2"}],[{"type":"String","basicValue":"3"}]]}}}

Python Code

Show Code

import networkx as nx

def shortest_path(edges, source, target, directed=False):
    """
    Find the shortest path and its length between two nodes in a network.

    See: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.shortest_paths.generic.shortest_path.html

    This example function is provided as-is without any representation of accuracy.

    Args:
        edges (list[list]): 2D array of edges. Each row should be [source, target] or [source, target, weight].
        source (str): The starting node ID.
        target (str): The ending node ID.
        directed (bool, optional): If True, treat the graph as directed. Default is False.

    Returns:
        dict: Data type containing the shortest path length (basicValue) and the path node sequence.
    """
    try:
        def to2d(x):
            return [[x]] if not isinstance(x, list) else x

        edges = to2d(edges)

        if not isinstance(edges, list) or not edges:
            return "Error: edges must be a non-empty 2D list"

        # Determine if weighted by looking at first row
        is_weighted = len(edges[0]) >= 3

        G = nx.DiGraph() if directed else nx.Graph()

        if is_weighted:
            G.add_weighted_edges_from([(str(row[0]), str(row[1]), float(row[2])) for row in edges if len(row) >= 3])
            weight_arg = 'weight'
        else:
            G.add_edges_from([(str(row[0]), str(row[1])) for row in edges if len(row) >= 2])
            weight_arg = None

        source_str = str(source)
        target_str = str(target)

        if source_str not in G:
            return f"Error: Source node '{source_str}' not found in graph"
        if target_str not in G:
            return f"Error: Target node '{target_str}' not found in graph"

        try:
            length = nx.shortest_path_length(G, source=source_str, target=target_str, weight=weight_arg)
            path = nx.shortest_path(G, source=source_str, target=target_str, weight=weight_arg)
        except nx.NetworkXNoPath:
            return f"Error: No path exists between '{source_str}' and '{target_str}'"

        return {
            "type": "Double",
            "basicValue": float(length),
            "properties": {
                "Length": { "type": "Double", "basicValue": float(length) },
                "Path": {
                    "type": "Array",
                    "elements": [[{"type": "String", "basicValue": str(node)}] for node in path]
                }
            }
        }
    except Exception as e:
        return f"Error: {str(e)}"

Online Calculator

edges *

2D array of edges. Each row should be [source, target] or [source, target, weight].

source *

The starting node ID.

target *

The ending node ID.

directed

If True, treat the graph as directed.