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
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"
valid_rows = [row for row in edges if isinstance(row, list) and len(row) >= 2]
if not valid_rows:
return "Error: No valid edges found in input"
is_weighted = any(len(row) >= 3 and row[2] not in (None, "") for row in valid_rows)
G = nx.DiGraph() if directed else nx.Graph()
if is_weighted:
weighted_edges = []
for row in valid_rows:
if len(row) >= 3 and row[2] not in (None, ""):
try:
weight = float(row[2])
except (TypeError, ValueError):
return f"Error: Invalid edge weight '{row[2]}'"
else:
weight = 1.0
weighted_edges.append((str(row[0]), str(row[1]), weight))
G.add_weighted_edges_from(weighted_edges)
weight_arg = 'weight'
else:
G.add_edges_from([(str(row[0]), str(row[1])) for row in valid_rows])
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)}"