Skip to content

GraphDistance

Status: Stable

documented, exercised by the test suite and/or worked examples, with no known limitations recorded.

Description

GraphDistance[g, s, t]

gives the length of a shortest path from s to t (Infinity if unreachable). GraphDistance[g, s] gives the list of distances from s to every vertex, in VertexList order. Edge weights are used as lengths when g has EdgeWeight.

Examples (10)

Every input below was run against the current Mathilda build and its output recorded.

Basic examples (2)

In[1]:= GraphDistance[Graph[{1->2, 2->3, 3->1, 3->4}], 1]
Out[1]= {0, 1, 2, 3}

In[2]:= GraphDistance[Graph[{1->2, 2->3, 3->1, 3->4}], 4, 1]
Out[2]= Infinity

Options (3)

In[3]:= GraphDistance[Graph[{1,2,3},{1<->2,2<->3,1<->3}, EdgeWeight->{1,1,5}], 1]
Out[3]= {0, 1.0, 2.0}

In[4]:= GraphDistance[Graph[{1,2,3},{1->2,2->3}, EdgeWeight->{5,7}], 1, 3]
Out[4]= 12.0

In[5]:= GraphDistance[Graph[{1,2},{1<->2}, EdgeWeight->{a}], 1]
Out[5]= GraphDistance[Graph[<2 vertices, 1 edge>], 1]

Applications (5)

Opposite vertices of a 6-cycle are 3 hops apart

In[6]:= GraphDistance[CycleGraph[6], 1, 4]
Out[6]= 3

A path's endpoints

In[7]:= GraphDistance[PathGraph[{1, 2, 3, 4}], 1, 4]
Out[7]= 3

Two-argument form: all distances from a source

In[8]:= GraphDistance[CycleGraph[5], 1]
Out[8]= {0, 1, 2, 2, 1}

Weighted: Dijkstra, a machine real

In[9]:= GraphDistance[Graph[{1 <-> 2, 2 <-> 3}, EdgeWeight -> {5, 7}], 1, 3]
Out[9]= 12.0

An unreachable target is Infinity

In[10]:= GraphDistance[Graph[{1, 2, 3}, {1 <-> 2}], 1, 3]
Out[10]= Infinity

Algorithm

shortestpath.c - FindShortestPath[g,s,t] and GraphDistance[g,s,t].

Two algorithms, dispatched on graph_weights_usable(g):

  - Unweighted (default): breadth-first search over the successor adjacency
    (GraphAdj.out[]): for a directed graph this follows edge direction; for
    an undirected graph out[] is symmetric, so it is an ordinary shortest
    path.
  - Weighted (g carries a non-negative-numeric EdgeWeight): Dijkstra over a
    local, call-scoped weighted adjacency (WAdj below) -- NOT over
    GraphAdj, which has no weight storage and is shared by 5 other
    builtins (ConnectedComponents, WeaklyConnectedComponents,
    FindSpanningTree, ConnectedGraphQ, VertexConnectivity); widening it
    would risk the exact class of shared-choke-point defect a
    plan-reviewer pass caught during the EdgeWeight ticket. Falls back to
    BFS for a symbolic or negative weight rather than erroring.

Wolfram's naming split is kept: FindShortestPath returns the vertex path, GraphDistance the length/total weight.

Unreachable target: FindShortestPath -> {} (empty list), GraphDistance -> Infinity.

Memory (SPEC section 4): returns freshly-allocated results; frees res.

Implementation notes

Algorithm. GraphDistance[g, s, t] gives the length of a shortest path from s to t. The core builtin_graph_distance dispatches on graph_weights_usable(g). The unweighted default runs a breadth-first search over the successor adjacency GraphAdj.out[] — for a directed graph this follows edge direction, and for an undirected graph out[] is symmetric, so it is an ordinary shortest path — and returns the integer hop count. When g carries a non-negative numeric EdgeWeight, it runs Dijkstra over a call-scoped weighted adjacency WAdj (built fresh rather than widening the shared GraphAdj, which has no weight storage) and returns the accumulated distance as a machine real. An unreachable target is Infinity; a symbolic or negative weight falls back to unit BFS rather than erroring. The registered head is actually the wrapper builtin_gmet_graph_distance (gmet_distance.c): it answers the single-source form GraphDistance[g, s] (all distances from s) itself and forwards the three-argument form here.

Data structures. The unweighted path uses graph_build_adj's CSR adjacency (out[]/in[] over one block allocation) with parent[]/dist[] arrays (-1 = unreached). The weighted path builds WAdj in two passes — an outdeg count, then a fill — indexing endpoints through a GraphVIdx and owning the resolved per-edge weight expressions; Dijkstra keeps a done[] flag array and double dist[] (DBL_MAX = unreached).

Complexity / limits. BFS is O(V + E). Dijkstra is implemented as a plain O(V²) array scan (no binary heap), matching this subsystem's small-graph exact-algorithm precedent. A weighted distance is a machine double (so 12., not 12), bit-for-bit consistent with GraphDistance[g, s] and GraphDistanceMatrix. Negative edge weights are out of scope — they silently demote the query to an unweighted hop count.

  • (w) weight-aware. GraphDistance[g, s] is the single-source form added by the graph-metrics module (src/graph/gmet_*.c); GraphDistance[g, s, t] is unchanged. GraphDistance is re-registered by a wrapper that delegates its pre-existing form ([g, s, t]) to the original builtin.
  • [g, s, t] uses the same weight-aware dispatch as FindShortestPath (Dijkstra when every weight is non-negative and numeric, BFS otherwise) and on a weighted graph returns a machine real, as the Wolfram Language does (weights {5, 7} give 12.), identical to GraphDistance[g, s] and GraphDistanceMatrix.
  • Single-source form, weighted: machine reals, except the source's own entry, which is an exact 0 as in Wolfram. A symbolic, complex or negative weight leaves the single-source form unevaluated.
  • Unweighted single-source results are Integers, packed when every vertex is reachable. Edge direction is followed; an undirected edge is usable both ways.

Attributes: Protected.

References

See also: VertexList, FindShortestPath, GraphDistanceMatrix

Notes & additional examples

Notes

Without edge weights the distance is the BFS hop count, an integer; for a directed graph the search follows edge direction. When the graph carries a non-negative numeric EdgeWeight, the distance is the Dijkstra total and comes back as a machine real (so 12., not 12), agreeing bit-for-bit with the single-source form and GraphDistanceMatrix.

GraphDistance[g, s, t] gives one length; GraphDistance[g, s] gives the list of distances from s to every vertex in canonical order. An unreachable target is Infinity; a symbolic or negative weight demotes the query to an unweighted hop count rather than erroring.