Skip to main content

Shortest Paths and Distance

A shortest path minimizes a declared quantity. It may minimize hops, travel time, money, or another additive cost; it does not automatically find the strongest relationship chain. On the interaction fixture, weight means strength, so using it directly as distance would make a stronger tie look farther away.

Prerequisites​

Complete traversal, components, and reachability. Keep its directed weighted multigraph interpretation and quality filters in view.

Learning goals​

  • Distinguish hop count, additive distance, and relationship strength.
  • Aggregate parallel event edges under an explicit rule before a simple-graph algorithm.
  • Handle unreachable ordered pairs instead of replacing infinity with zero.
  • Read a shortest path as model output, not evidence that anything flowed along it.

Analysis contract​

  • Graph type: a directed simple graph derived from the valid MultiDiGraph; parallel-edge aggregation sums positive strengths and the self-loop is retained.
  • Normalization: none. Hop length counts edges; the teaching cost is 1 / summed_strength and is rounded only for display.
  • Disconnected case: no directed path means infinite or undefined distance; nx.has_path is checked before requesting a path.
  • Interpretation limit: the reciprocal transform is an explicit modeling choice. A shortest modeled route is evidence, not observed transmission, importance, or causality.

From strength to cost​

For positive aggregated strength suvs_{uv}, this lesson defines cuv=1/suvc_{uv}=1/s_{uv}. That makes stronger ties cheaper, but it assumes costs add and reciprocal strength is meaningful. Other domains might use elapsed time directly, transform a probability with −log⁡(p)-\log(p), or refuse to define a path cost at all. Dijkstra's algorithm requires nonnegative costs; negative costs need a compatible method and negative cycles make a finite shortest path impossible.

Direction remains part of the question. Ada reaches Dia in three hops. Dia cannot reach Ada in the observed graph, and no one reaches the declared isolate Gia.

Worked example​

import csv
from pathlib import Path

import networkx as nx

fixture = Path("tests/fixtures/graph-data-science")
with (fixture / "interaction-nodes.csv").open(encoding="utf-8") as handle:
node_ids = [row["node_id"] for row in csv.DictReader(handle)]
with (fixture / "interaction-relationships.csv").open(encoding="utf-8") as handle:
rows = [row for row in csv.DictReader(handle) if row["record_status"] == "valid"]

graph = nx.DiGraph()
graph.add_nodes_from(node_ids)
for row in rows:
source, target = row["source"], row["target"]
strength = float(row["weight"])
if graph.has_edge(source, target):
graph[source][target]["strength"] += strength
else:
graph.add_edge(source, target, strength=strength)
for source, target, data in graph.edges(data=True):
data["cost"] = 1 / data["strength"]

hop_path = nx.shortest_path(graph, "ada", "dia")
cost_path = nx.shortest_path(graph, "ada", "dia", weight="cost", method="dijkstra")
cost = nx.shortest_path_length(graph, "ada", "dia", weight="cost", method="dijkstra")
print(f"hop_path={hop_path} hops={len(hop_path) - 1}")
print(f"cost_path={cost_path} cost={cost:.3f}")
print(f"dia_to_ada={nx.has_path(graph, 'dia', 'ada')} ada_to_gia={nx.has_path(graph, 'ada', 'gia')}")

Expected output:

hop_path=['ada', 'ben', 'cy', 'dia'] hops=3
cost_path=['ada', 'ben', 'cy', 'dia'] cost=1.667
dia_to_ada=False ada_to_gia=False

The hop and cost routes happen to agree here. That agreement is a fixture result, not a general property.

Limitations​

  • shortest_path may return one of several tied routes; a single returned list does not prove uniqueness.
  • Summing parallel strengths answers a different question from keeping event-specific costs or taking a minimum.
  • Average path length is not defined over the whole disconnected directed graph without a stated reachable-pair or component convention.
  • A missing edge can make a real route look unreachable. The fixture's missing relationship is not imputed.

Practice​

Compare Ada-to-Fox under hop count and reciprocal-strength cost. Then state whether summing two parallel events is defensible for your application before interpreting the answer.

Next steps​

Continue to centrality and its failure modes to see how path conventions propagate into node-level summaries.

Primary sources​

Checked 2026-10-18: NetworkX, shortest-path reference; NetworkX, shortest_path; E. W. Dijkstra, A note on two problems in connexion with graphs.