Dijkstra's algorithm facts for kids

Dijkstra's algorithm is an algorithm that works on groups of things connected by distances. It finds the shortest ways to move from one first thing to each other thing in the graph. It is faster than many other ways to do this, but it needs all of the distances connecting the things to be zero or more.

Steps

• Make a list of all of the things in the graph
• Write 0 next to the first thing
• Keep doing these steps:
  • Find the thing that you have not yet drawn a mark next to that has the smallest number written next to it
  • Draw a mark next to this thing
  • Do these steps for each other thing connected to this place:
    • Add the number written next to this thing and the distance of the connection together
    • If the connected thing does not have a number written next to it, write the new number and the name of this thing next to the connected thing
    • If the connected thing has a number written next to it and the new number is smaller than the written number:
      • Draw a line over what is already written
      • Write the new number and the name of this thing instead
  • Stop when you have drawn a mark next to every thing in the list

When you have done all of these steps you can use the list to find the shortest way from the first thing to any other thing. First write down the other thing. Then keep doing these steps:

• Find the last thing you wrote down in the list
• Write down the thing written next to it
• Stop when you find the first thing

The connections between the things you have written down are the shortest way from the first thing to the other thing.

Images for kids

• 

  Illustration of Dijkstra's algorithm finding a path from a start node (lower left, red) to a goal node (upper right, green) in a robot motion planning problem. Open nodes represent the "tentative" set (aka set of "unvisited" nodes). Filled nodes are the visited ones, with color representing the distance: the greener, the closer. Nodes in all the different directions are explored uniformly, appearing more-or-less as a circular wavefront as Dijkstra's algorithm uses a heuristic identically equal to 0.

• 

  A demo of Dijkstra's algorithm based on Euclidean distance. Red lines are the shortest path covering, i.e., connecting u and prev[u]. Blue lines indicate where relaxing happens, i.e., connecting v with a node u in Q, which gives a shorter path from the source to v.

See also

In Spanish: Algoritmo de Dijkstra para niños