Dijkstra's algorithm

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 2411.06128 §V 2411.06128 eq. 4 2411.06128 eq. 7.

The algorithm needs non-negative edge weights. The paper states this limit directly 2411.06128 §V. The paper's equations give distances only; how to recover the path itself is not stated 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 2411.06128 §VI. The authors call the combination PP-D. Card: Research on reinforcement learning based warehouse robot navigation algorithm in complex warehouse layout.

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 2411.06128 §VI. The PPO side is covered on its concept page.

When to use which

The paper's comparison is one table on one test set, with no seeds, variance or significance test 2411.06128 tab. II 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 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.

# 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 2411.06128 §V.

Papers

• Research on reinforcement learning based warehouse robot navigation algorithm in complex warehouse layout: uses Dijkstra for the static global path and PPO for the adaptive action policy, compared with DQN and A* on one test set.