Image: Dijkstras progress animation

Description: Illustration of Dijkstra's algorithm. The graph is created by uniform square discretization of a 2-dimensional planar region, placing a node in each discretized cell, and connecting each node with its 8 neighbors using bidirectional edges. Cost of edges are same as their Euclidean lengths. The gray shape represents an obstacle. The filled circles in red & green represent expanded nodes (nodes in closed set). The color indicate the distance (in the graph) of a node from the start node (red: lower, green: higher). The empty nodes with blue boundary are the ones in open set. The nodes of the graph are generated on the fly, and nodes falling inside the obstacle are discarded as inaccessible. Note that Dijkstra's is a special case of the A* search algorithm when the heuristic is identically 0. Note how the nodes are expanded almost uniformly in all directions. The number of nodes expanded is significantly higher when compared with the same search problem solved using A* search algorithm. Created using YGSBPL graph-search library and OpenCV.
Title: Dijkstras progress animation
Credit: Own work
Author: Subh83
Permission: This file is licensed under the Creative Commons Attribution 3.0 Unported license. You are free: to share – to copy, distribute and transmit the work to remix – to adapt the work Under the following conditions: attribution – You must attribute the work in the manner specified by the author or licensor (but not in any way that suggests that they endorse you or your use of the work). http://creativecommons.org/licenses/by/3.0 CC BY 3.0 Creative Commons Attribution 3.0 truetrue
Usage Terms: Creative Commons Attribution 3.0
License: CC BY 3.0
License Link: http://creativecommons.org/licenses/by/3.0
Attribution Required?: Yes