Graphs: the answer follows the edge model, not the question

Unit seven showed that the promise is only as wide as the condition. Graph questions all look alike. Which vertices can reach which, in what order may they be visited, and how far apart are two of them? Each answer is a function of a model of what an edge is: whether its cost may be negative, whether it has a cost at all, and whether the graph is supplied or built. The claim of this unit is that the answer follows that model rather than the question. Run the standard distance algorithm where an edge may cost less than nothing, and it returns a confident wrong answer, since the assumption that made it correct was deleted while the algorithm was not. An algorithm's guarantee is a promise about a class of graphs, and outside that class it still runs, terminates and answers, which is worse than an error.

One question, a different algorithm for each edge model

The shortest-path question is one question: given two vertices and the cost of every edge, find the cheapest route. Dijkstra (1959) grows a set of vertices whose distance is settled, always extending it by the nearest unsettled vertex. The method is correct because no cost is negative, so a settled distance can never later be undercut. Bellman (1958) posed the routing problem without that restriction and relaxed each edge repeatedly until the estimates stopped falling. That finds the route when costs may be negative, and it signals a negative cycle when they never settle. Floyd (1962) asked for every pair at once, and he answered it by relaxing a matrix of distances through one intermediate vertex at a time. Both classical bounds have since moved. Bernstein, Nanongkai and Wulff-Nilsen (2025) give the first near-linear time algorithm for single-source shortest paths with negative edge weights, replacing the bound that repeated relaxation carried for three decades, and Duan, Mao, Mao, Shu and Yin (2025) give a deterministic O(m log^(2/3) n) algorithm for non-negative weights, the first to break the O(m + n log n) barrier of Dijkstra on sparse graphs. Dijkstra is therefore no longer the optimal method for the model its guarantee made it famous in.

Each is correct inside a stated model and silent outside it, and the model is invisible in the question a user asks. Whether the weights are non-negative, whether a route may profit by looping, and whether the answer wanted is one pair or every pair are properties of the instance that decide which procedure is right.

Correctness is a supplement the model supplies

Hart, Nilsson and Raphael (1968) move part of the model outside the graph. Their search orders vertices by a heuristic estimate of the remaining cost, and finds an optimal path whenever that estimate never exceeds the true remaining cost, expanding the fewest vertices any admissible search can guarantee. What was added is a function whose property the designer must establish. An over-optimistic estimate breaks the guarantee while leaving a plausible-looking route behind.

The failure is mechanical. The proof that the first goal reached is optimal rests on the estimate never exceeding the true remaining cost. Let it exceed that cost and the vertex's score can rise above the cost of the true best route, so the search settles a goal by a longer path, terminates, and reports a route that is not the cheapest one.

Cherkassky, Goldberg and Radzik (1996) compared shortest-path algorithms across problem classes and found that the classes expose different strengths and weaknesses, so the algorithm of choice depends on the instance family rather than on one measure of quality.

The supporting structure, not the graph, decides the cost

Some graph questions are about structure rather than distance, and there the traversal order decides the work. Tarjan (1972) showed that depth-first search gives algorithms for the strongly connected components of a directed graph and the biconnected components of an undirected one, using the order in which vertices are entered and left, in time and space bounded by constants times the vertices and edges. The traversal is the model.

Connectivity is the case where a supporting structure, not the graph, sets the price. Galler and Fisher (1964) represented equivalence classes as a tree and identified them all in one scan, reporting a 40 per cent reduction in computation. Tarjan (1975) proved that the same idea with union by rank and path compression runs in almost linear time, its bound involving the inverse of the Ackermann function. Kruskal (1956) built a minimum spanning tree by taking edges in increasing weight and accepting each that joins two components, so his cost is the cost of deciding whether two vertices are already connected.

Real graphs do not have the properties the algorithms assume

Reachability theories assume a graph, and the graphs people actually hold are not uniform. Barabasi and Albert (1999) showed that growth and preferential attachment together generate a power-law degree distribution, so a few vertices carry most of the edges: a search from an ordinary vertex reaches a hub quickly, and one from a hub fans out over most of the graph. Watts and Strogatz (1998) described a regular lattice with a few edges rewired at random, and showed the result is both highly clustered and short in characteristic path length, a combination they found in three real networks.

The measured claim is thinner than the model. Travers and Milgram (1969) asked 296 starters to pass a letter towards one target: 64 of the 217 chains actually started reached him, and the completed chains averaged 5.2 intermediaries. The famous short average describes the chains that survived rather than the pairs that never connected, and the authors call their own starters a heavily middle-class sample.

The answer can be defined rather than found

Ranking is where the algorithm defines its answer. Page, Brin, Motwani and Winograd (1999) defined PageRank as the stationary distribution of a random walk over the link graph, mixed by a damping factor that sends the walker to a random page. The factor and the rank-source vector are parameters the implementer sets, so a different choice orders the same links differently.

Geisberger, Sanders, Schultes and Delling (2008) order vertices by importance, replace paths through low-importance vertices by shortcuts, and answer a query by a bidirectional search on the hierarchy, reporting five times lower query times than the best previous hierarchical method. The query is fast because it runs on a graph the algorithm built, not the one supplied.

Contested question: is the fast answer a better algorithm or a different graph?

The first position holds that the improvement is algorithmic. Dijkstra (1959), Bellman (1958) and Floyd (1962) all search the graph they were given and differ only in the cost model they accept, so the design lies in the direction and order of the search. A speed-up is then evidence about an algorithm.

The opposing position holds that the improvement comes from changing the object searched. Geisberger and colleagues (2008) answer on a shortcut hierarchy nobody supplied, so their query time is a property of a graph they built, and Hart, Nilsson and Raphael (1968) hang the guarantee on a function whose admissibility the designer must establish. A claim that one algorithm is faster becomes a claim about a model that may not transfer.

A third position cuts across both. Cherkassky, Goldberg and Radzik (1996) found that the strengths and weaknesses of the algorithms differ across problem classes, so which view holds is decided by the instance family rather than by a general argument. A study would settle the disagreement: fix one query set and one graph, run the classical, heuristic-guided and precomputed searches on it, and report the resources each spent, per graph family. No source here provides that comparison, and none runs an algorithm deliberately outside its model to record the wrong answer, so the unit's claim that the wrong model yields a confident wrong answer rests on assumptions rather than on a measured failure.

The positions differ in what supports them. Dijkstra (1959), Bellman (1958) and Floyd (1962) prove correctness inside a stated model, and Cherkassky, Goldberg and Radzik (1996) measure across instance families, while Geisberger and colleagues (2008) measure a speed-up on a hierarchy they built. The strongest objection is that a speed-up usually comes from replacing the graph, so the model a question appears to follow may be one engineered to answer it quickly rather than one describing the data. While the dispute is open, a designer records which graph was searched and whether the answer rests on a supplied or a constructed model.

Where the argument is heading

The named work points to the model being built rather than given. Geisberger and colleagues (2008) are the clearest case, a query structure assembled out of the graph and smaller than it, and Page and colleagues (1999) a computation whose parameters belong to the designer. The modelling line runs the other way: Barabasi and Albert (1999) and Watts and Strogatz (1998) describe classes of real graphs whose statistics an algorithm might be tuned to.

The sources this unit rests on

• Barabasi, A. L. and Albert, R. (1999). Emergence of Scaling in Random Networks. Science. doi:10.1126/science.286.5439.509 Barabasi and Albert show that growth plus preferential attachment yields a power-law degree distribution, found in real networks, so a few vertices carry most of the edges. It explains why a hub is a shortcut.
• Bellman, R. (1958). On a routing problem. Quarterly of Applied Mathematics. doi:10.1090/qam/102435 Bellman poses the routing problem without requiring non-negative costs, relaxing edges until the estimates stop falling, and exposes a negative cycle when they never settle. Its assumption is weaker than Dijkstra's.
• Bernstein, A., Nanongkai, D. and Wulff-Nilsen, C. (2025). Negative-Weight Single-Source Shortest Paths in Near-linear Time. Journal of the ACM. doi:10.1145/3742890 Bernstein, Nanongkai and Wulff-Nilsen give a randomised near-linear time algorithm that computes single-source shortest paths with negative integer weights or reports a negative cycle, the first combinatorial method to break the three-decade bound.
• Cherkassky, B. V., Goldberg, A. V. and Radzik, T. (1996). Shortest paths algorithms: Theory and experimental evaluation. Mathematical Programming. doi:10.1007/bf02592101 Cherkassky, Goldberg and Radzik compare a family of shortest-path algorithms across problem classes and find that the best bounds do not translate into the fastest running times, the ranking depending on the instance family.
• Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik. doi:10.1007/bf01386390 Dijkstra gives the shortest-path method that settles vertices in increasing distance, and notes that no edge cost may be negative. It is the default for non-negative weights, so its guarantee holds only inside a stated model.
• Duan, R., Mao, J., Mao, X., Shu, X. and Yin, L. (2025). Breaking the Sorting Barrier for Directed Single-Source Shortest Paths. Proceedings of the 57th Annual ACM Symposium on Theory of Computing. doi:10.1145/3717823.3718179 Duan, Mao, Mao, Shu and Yin give a deterministic near-optimal algorithm for directed non-negative shortest paths, the first to break the O(m + n log n) bound of Dijkstra on sparse graphs.
• Floyd, R. W. (1962). Algorithm 97: Shortest path. Communications of the ACM. doi:10.1145/367766.368168 Floyd gives a short procedure that computes all-pairs distances by relaxing the distance matrix through one intermediate vertex at a time. It is the unit's second appearance of dynamic programming.
• Galler, B. A. and Fisher, M. J. (1964). An improved equivalence algorithm. Communications of the ACM. doi:10.1145/364099.364331 Galler and Fisher represent equivalence classes as trees and identify them all in one scan, reporting a 40 per cent reduction in computation. It treats connectivity as its own problem rather than an application of graph search.
• Geisberger, R., Sanders, P., Schultes, D. and Delling, D. (2008). Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks. Experimental Algorithms (WEA), Lecture Notes in Computer Science. doi:10.1007/978-3-540-68552-4_24 Geisberger, Sanders, Schultes and Delling replace paths through unimportant vertices by shortcuts and answer a query by a bidirectional search on the hierarchy, reporting query times five times lower than the best previous method.
• Hart, P., Nilsson, N. and Raphael, B. (1968). A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics. doi:10.1109/tssc.1968.300136 Hart, Nilsson and Raphael formalise the evaluation-function approach to heuristic search and prove that when the estimate never exceeds the true remaining cost the search returns an optimal path, expanding the fewest vertices. Its guarantee is a property of a supplied function.
• Kruskal, J. B. (1956). On the shortest spanning subtree of a graph and the travelling salesman problem. Proceedings of the American Mathematical Society. doi:10.1090/s0002-9939-1956-0078686-7 Kruskal builds a minimum spanning tree by taking edges in increasing weight and accepting each that joins two components, with an exchange argument for correctness. Its practical price is set by the structure that tests connectivity.
• Page, L., Brin, S., Motwani, R. and Winograd, T. (1999). The PageRank citation ranking: bringing order to the web. Stanford InfoLab Technical Report 1999-66. https://web.archive.org/web/2020id_/http://ilpubs.stanford.edu:8090/422/1/1999-66.pdf Page, Brin, Motwani and Winograd define PageRank as the stationary distribution of a random walk over the link graph, mixed by a damping factor and a rank-source vector. The order depends on parameters the designer chooses.
• Tarjan, R. (1972). Depth-First Search and Linear Graph Algorithms. SIAM Journal on Computing. doi:10.1137/0201010 Tarjan shows that depth-first search, with the order in which vertices are entered and left, yields linear-time algorithms for strongly connected and biconnected components, bounded by constants times the vertices and edges. It is a construction.
• Tarjan, R. E. (1975). Efficiency of a Good But Not Linear Set Union Algorithm. Journal of the ACM. doi:10.1145/321879.321884 Tarjan proves that set union with union by rank and path compression runs in almost linear time, its bound involving the inverse of the Ackermann function. It makes connectivity and the Kruskal algorithm affordable.
• Travers, J. and Milgram, S. (1969). An Experimental Study of the Small World Problem. Sociometry. doi:10.2307/2786545 Travers and Milgram asked 296 starters to pass a letter towards one target; 217 chains were started, 64 reached him, and the completed chains averaged 5.2 intermediaries. The famous short average describes the surviving chains.
• Watts, D. J. and Strogatz, S. H. (1998). Collective dynamics of 'small-world' networks. Nature. doi:10.1038/30918 Watts and Strogatz show that a regular lattice with a few randomly rewired edges is highly clustered and yet has short characteristic path lengths, a combination they find in three real networks. Short paths are a property of topology.