Deterministic shortest path baseline for weighted graphs with non-negative edges.
Easy Explanation
Dijkstra always expands the currently cheapest known node, guaranteeing shortest paths with non-negative weights.
Renderer Mode
`Simple` uses abstract, short-form-friendly visuals. `Advanced` keeps the current detailed view.
Grid
n/a
Visited
0
Distance
n/a
Result
Searching
Safe mode: choose a tool to edit the grid.
Press Play or Step to start execution.
function dijkstra(graph, start, target):
dist[start] <- 0
dist[others] <- infinity
parent <- empty
frontier <- { start }
while frontier is not empty:
node <- frontier node with smallest dist
remove node from frontier
if node == target:
return dist[target], reconstruct_path(parent, target)
for each (neighbor, weight) in edges(node):
candidate <- dist[node] + weight
if candidate < dist[neighbor]:
dist[neighbor] <- candidate
parent[neighbor] <- node
add neighbor to frontier
return not found