Publication record · 18.cifr/1959.dijkstra.shortest-path

A note on two problems in connexion with graphs

v1.0.0

E. W. Dijkstra (Mathematisch Centrum, Amsterdam)

RAI18.cifr/1959.dijkstra.shortest-path

Numerische Mathematik· 1959· doi:10.1007/BF01386390

We will consider a finite undirected graph with positive lengths assigned to its edges. We wish to find a tree of minimum total length between the n nodes of the graph (shortest spanning subtree problem) and the path of minimum total length between two given nodes (shortest path problem).

shortest pathgraph theorygreedy algorithmminimum spanning treenetwork routing

✦ Research context

What this agent contributes to the literature.

Problem solved

Before this work, no practical polynomial-time algorithm existed for exact shortest-path computation in weighted graphs. Network designers and operations researchers had to enumerate candidate paths explicitly. Dijkstra's O(V^2) greedy selection scheme gave the first efficient exact solution, enabling practical routing, scheduling, and planning systems.

Novelty

Dijkstra introduced an efficient greedy algorithm for single-source shortest paths in non-negatively weighted graphs. The paper solved two classical graph problems (shortest paths and minimum spanning tree) in a unified greedy framework without exhaustive path enumeration. The settled-set / relaxation structure remains the canonical approach over 60 years later.

Related research

Computing related research...

Canvas contract1-in / 1-out · unpacked into graph, params legacy ports

Sample data

Loading sample data...

Total calls

This month

Citations

Last called

—

Image digest

sha256:fe6148ef2f8f1c1b2401165cf07d9804e11c3695cb22af8121aa484eb5156e08

Invoke command

python main.py

Inputs

input:application/json

Outputs

output:application/json

Citation

Loading DOI…

Invoke

CPU compute only

How to get GPU access: Your university, lab, or company can become a CIFR institutional member. Members get GPU-accelerated runs for all their researchers. Contact us

Pre-filled with the paper's canonical scenario. Click Invoke agent to reproduce the original result, or edit the JSON below to run a counterfactual.

inputapplication/jsonoptional

Unified canvas input containing graph topology and query parameters

Leave empty to run the paper's canonical scenario.

Recent invocations(0)

No invocations yet — be the first to call this agent.