---
kind: concept
slug: dijkstra-algorithm
title: Dijkstra's algorithm
summary: >-
  Shortest-path search from one start node over a graph with non-negative edge weights, giving the distance to every reachable node. Used as the global planner on a static warehouse layout, with a PPO controller on top; the one card that uses it reports better scores than DQN and A*, from a single table with no statistics.
tags: [graph-search, path-planning, shortest-path, robotics]
papers: ["2411.06128"]
related: [a-star-search, proximal-policy-optimization]
status: draft
updated_at: 2026-10-25
---

## Overview

Dijkstra's algorithm finds the shortest distance from one start node to every
reachable node. It keeps a distance estimate per node, starting at zero for the
start and infinity elsewhere, and repeatedly settles the unvisited node with the
smallest estimate. Each settled node can shorten its neighbours' estimates
[arxiv:2411.06128 §V] [arxiv:2411.06128 eq. 4] [arxiv:2411.06128 eq. 7].

The algorithm needs non-negative edge weights. The paper states this limit
directly [arxiv:2411.06128 §V]. The paper's equations give distances only; how
to recover the path itself is not stated [arxiv:2411.06128 §V].

## Variants

Only one card in the library lists this concept, and it uses the algorithm as
a fixed planner rather than proposing a variant of it.

### Global planner with a learned controller

The paper plans one shortest path on the static warehouse layout with
Dijkstra, then lets a PPO agent choose the robot's actions while it adapts to
changes in the environment [arxiv:2411.06128 §VI]. The authors call the
combination PP-D. Card: [Research on reinforcement learning based warehouse robot navigation algorithm in complex warehouse layout](/papers/2411.06128).

The paper does not say how the Dijkstra path reaches the PPO agent. It could be
an observation input, a reward term, an action restriction or a fallback
controller; the paper names none of these [arxiv:2411.06128 §VI]. The PPO side
is covered on [its concept page](/concepts/proximal-policy-optimization).

## When to use which

| Situation | Use | Why |
|---|---|---|
| Static map, non-negative edge costs, need the shortest path | Dijkstra | The algorithm gives exact distances for this case [arxiv:2411.06128 §V]. |
| Layout or obstacles change while the robot runs | Dijkstra for the static part, plus an adaptive controller | The paper says the Dijkstra path is optimal only for the static layout; adaptation comes from the learned part [arxiv:2411.06128 §VI]. Its benefit is reported by the authors only. |
| Negative edge weights | Not Dijkstra | The paper states the algorithm assumes non-negative weights [arxiv:2411.06128 §V]. |
| Goal-directed search with a good heuristic | Compare with A* | Dijkstra is A* with no heuristic; see [A* search](/concepts/a-star-search) for the heuristic variants. |

The paper's comparison is one table on one test set, with no seeds, variance
or significance test [arxiv:2411.06128 tab. II] [arxiv:2411.06128 §VII-B].
Its reported scores (PP-D 96.42% accuracy ratio against 89.76% for DQN and
86.93% for A*) are therefore author-reported, not established
[arxiv:2411.06128 tab. II].

## Implementation sketch

The paper gives the core loop as equations 4 to 7. The sketch below follows
them. The paper does not describe a priority queue or how the layout is turned
into a graph, so both are left open. Path recovery would need a predecessor
record, which the paper does not state.

```pseudocode
# Dijkstra shortest distances from a start node  [arxiv:2411.06128 §V]
# Input:  graph with non-negative edge weights w, start node s
# Output: shortest distance to every reachable node

def dijkstra(graph, start):
    # Start node has distance 0, all others infinity  [eq. 4] [eq. 5]
    distance = {node: INFINITY for node in graph.nodes}
    distance[start] = 0
    unvisited = set(graph.nodes)  # the paper's priority queue  [§V]
    while unvisited:
        # Settle the unvisited node with the smallest distance  [§V]
        node = pop_min(unvisited, distance)
        for neighbour in graph.neighbours(node):
            # Candidate distance through node  [eq. 6]
            candidate = distance[node] + graph.weight(node, neighbour)
            # Keep the smaller of the two  [eq. 7]
            distance[neighbour] = min(distance[neighbour], candidate)
    return distance
```

## Contradictions

None known across the cards that list this concept. The paper's reference list
does not support its Dijkstra claim (the reference is on an unrelated topic),
so the claim rests on the paper's own text [arxiv:2411.06128 §V].

## Papers

- [Research on reinforcement learning based warehouse robot navigation algorithm in complex warehouse layout](/papers/2411.06128): uses Dijkstra for the static global path and PPO for the adaptive action policy, compared with DQN and A* on one test set.