Dijkstra's algorithm in a nutshell

Dijkstra's algorithm solves the single-source shortest path problem on a weighted graph with non-negative edge weights. Given a source node \(s\), it computes the shortest distance \(d(s, v)\) to every other node \(v\), and a predecessor for each node so you can reconstruct the actual path.

High-level algorithm

1. Initialize all distances to \(\infty\) except the source, set to 0.
2. Mark all nodes as unvisited.
3. Repeat:
   • Pick the unvisited node with the smallest tentative distance.
   • For each outgoing edge, try to relax it (update neighbor distance if a shorter path is found).
   • Mark the current node as visited.
4. Stop when all nodes are visited or when the target node has been extracted (if you only care about one destination).

Time complexity

The complexity depends on how you select the node with minimum tentative distance:

• Simple array / linear scan: \(O(V^2)\)
• Binary heap: \(O((V + E)\log V)\)
• Fibonacci heap: roughly \(O(E + V\log V)\)

This calculator uses the simple array-based approach for transparency of the logic and is suitable for educational examples and small- to medium-sized graphs.

Interpreting the calculator output

• Distance table: Shows the final minimal distance from the source to every node. If a node is unreachable, the distance is reported as \(\infty\).
• Predecessor column: Indicates, for each node, which previous node lies on a shortest path from the source. By following predecessors from the target back to the source you reconstruct the route.
• Shortest path summary: When a target node is specified, the calculator reconstructs and prints the path as a sequence of nodes plus the total distance.

Common pitfalls and FAQs

Why can't I use negative weights?

Dijkstra's algorithm assumes that once a node is extracted with the smallest tentative distance, that distance is final. Negative edge weights break this property because a path that looks optimal at one stage may be improved later by a negative edge. For graphs with negative weights, use algorithms such as Bellman–Ford.

Directed vs undirected graphs

In an undirected graph, every edge \((u, v)\) is interpreted as two directed edges \(u \to v\) and \(v \to u\) with the same weight. The calculator automatically mirrors edges when the "Treat graph as directed" option is off.

How large can my graph be?

The implementation here is designed for teaching and quick problem solving, not for huge production instances. A few dozen nodes and up to a couple of hundred edges are perfectly fine in a browser environment; for very large graphs, use specialized libraries or offline tools.