Dijkstra Shortest Path Calculator

How this Dijkstra shortest path calculator works

This tool applies Dijkstra’s algorithm to a small weighted graph that you enter as an adjacency matrix. You specify how many nodes the graph has, fill in the edge weights, choose a start node and an end node, and the calculator returns the total distance of the shortest path and the sequence of nodes along that path.

Nodes are numbered using zero-based indexing: if you choose N nodes, they are labeled 0, 1, 2, …, N−1. Distances must be nonnegative (zero or positive). Missing edges are treated as “no connection” rather than zero cost.

Dijkstra’s algorithm in a nutshell

Dijkstra’s algorithm solves the single-source shortest path problem on graphs with nonnegative edge weights. Starting from a chosen source node, it incrementally discovers the minimum distance to every other node by repeatedly selecting the closest not-yet-finalized node and updating (relaxing) the distances to its neighbors.

You can think of it as a wave that expands outward from the start node. At each step, the node with the smallest tentative distance is “locked in” as final, and its outgoing edges are used to try to improve the tentative distances of neighboring nodes.

Core distance update formula

The key operation is called relaxation. Suppose the current node is u and a neighbor is v with edge weight w_uv. If the best known distance to u is d(u) and the best known distance to v is d(v), then we update using:

Because all edge weights are nonnegative, once a node is chosen as the closest tentative node, its distance can never be improved later, so it becomes final.

How to use the calculator

1. Choose the number of nodes (2–6).

   Enter an integer between 2 and 6 in the Nodes field. The underlying matrix is treated as an N × N adjacency matrix for those nodes.

2. Fill in the adjacency matrix.

   For each ordered pair of nodes (i, j):

   • Enter a nonnegative number for the edge weight from node i to node j.
   • Leave the cell blank or enter a dash (-) if there is no edge from i to j.
   • Zero means a real zero-cost edge, not “no edge”.

   The graph is treated as directed unless you explicitly mirror weights. If you want an undirected edge between i and j, enter the same weight in both (i, j) and (j, i).

3. Set the start and end nodes.

   Use zero-based labels. For example, with N = 4, valid nodes are 0, 1, 2, and 3. Enter the indices of the start node and the end node in their respective fields.

4. Run the algorithm.

   Click the button to compute the shortest path. The tool runs Dijkstra’s algorithm from the chosen start node and reports the total distance to the end node together with the path as an ordered list of nodes.

Interpreting the result

The output contains two main pieces of information:

• Total distance: the sum of the weights along the reported path from the start node to the end node.
• Path: a sequence like 0 → 1 → 3 that lists the nodes in the order they are visited along the shortest route.

If there is no way to reach the end node from the start node following the edges you entered, the calculator will indicate that the end node is unreachable. In that case, you may want to:

• Check for missing edges you intended to include.
• Verify you did not accidentally reverse a directed edge.
• Confirm that the start and end indices are within the valid range 0 … N−1.

Worked example

Consider a graph with four nodes, labeled 0 through 3, and the following directed edges:

• 0 → 1 with weight 2
• 0 → 2 with weight 5
• 1 → 2 with weight 1
• 1 → 3 with weight 7
• 2 → 3 with weight 2

The adjacency matrix (rows are sources, columns are destinations) looks like this, where a dash means no edge:

      0   1   2   3
    ----------------
  0 |  -   2   5   -
  1 |  -   -   1   7
  2 |  -   -   -   2
  3 |  -   -   -   -
  

Suppose you set the start node to 0 and the end node to 3. Dijkstra’s algorithm proceeds roughly as follows:

1. Initialize distances: d(0) = 0, and d(1) = d(2) = d(3) = ∞. Mark all nodes as unvisited.
2. Pick the unvisited node with smallest tentative distance: node 0.
   • Relax edge 0 → 1: d(1) becomes 2.
   • Relax edge 0 → 2: d(2) becomes 5.
   Mark node 0 as visited.
3. Next smallest tentative distance is node 1 with d(1) = 2.
   • Relax edge 1 → 2: d(2) can improve to 2 + 1 = 3, so update d(2) = 3.
   • Relax edge 1 → 3: d(3) becomes 2 + 7 = 9.
   Mark node 1 as visited.
4. Next is node 2 with d(2) = 3.
   • Relax edge 2 → 3: d(3) improves from 9 to 3 + 2 = 5.
   Mark node 2 as visited.
5. Finally, node 3 has d(3) = 5. It has no outgoing edges, so the process ends.

The shortest path from 0 to 3 is 0 → 1 → 2 → 3 with total distance 2 + 1 + 2 = 5. The calculator will display this path and its length once you enter the matrix and press the compute button.

When to use Dijkstra vs. other algorithms

Dijkstra’s algorithm is one of several shortest path and graph search techniques. The table below summarizes where it fits compared with a few related algorithms.

This calculator specifically implements standard Dijkstra for small graphs with nonnegative weights. For negative weights or more advanced routing constraints, you would need a different algorithm or a more specialized tool.

Assumptions and limitations of this tool

• Nonnegative weights only: All edge weights must be zero or positive. Negative numbers are interpreted as “no edge”, not as negative cost.
• Small graphs: The calculator is intended for graphs with between 2 and 6 nodes, suitable for manual examples, teaching, or homework checks.
• Directed adjacency matrix: Each cell represents a directed edge from row node to column node. To model an undirected graph, enter symmetric weights in both directions.
• No support for negative cycles: Because negative weights are not allowed, scenarios involving negative cycles are outside the scope of this tool.
• Exact arithmetic as entered: The tool does not interpret units (meters, seconds, cost units). Whatever numbers you enter are treated as abstract weights and simply added along paths.

Common input mistakes to avoid

• Using zero to mean “no edge”. In this calculator, zero means a real zero-cost edge; use a blank or dash for no connection.
• Mixing one-based labels (1, 2, 3, …) in your notes with the zero-based indices (0, 1, 2, …) used by the tool.
• Forgetting to mirror entries when you intend an undirected graph.
• Entering start or end node indices outside the valid range 0 … N−1.

Within these limits, this Dijkstra shortest path calculator is ideal for checking hand calculations, building intuition before you code your own implementation, or demonstrating how the algorithm works in a classroom or study session.