This is a simple javascript implenetation of Dijkstra's Algorithm to find the minimum distance between two points. The edges are weighted randomly, and only exist fo 75% of the possible edges. Once the algorithm begins, "visited" vertices will turn gray, the vertex under current consideration yellow, and when complete, the path will be in red. Status messages are below, as well as info for any individual node.
Quick overview of the Algorithm: (click for description)
Start by setting the distance value for each vertex at Infinity.
Set the distance for the starting Vertex to 0.
Push all the vertices onto a sorted structure, usually some form of a heap. This particular implementation uses a simple array due to the limited size.
Repeat the following:
Pop the first element off the vertices stack.
If the current vertex = end vertex, we've found the path.
Traverse each of it's edges to the next vertex. For each of those vertices:
Calculate the tentative distance for that vertex: tentative distance = (current distance) + (edge weight).
Set the distance to be the minimum of either it's current distance, or the tentative distance. (denoted as the black number on each vertex).
Mark the current vertex as visited and never revisit. This implementation accomplishes this via the pop at the beginning, which remove it from the possible vertex pool. (vertex marked as gray when visited)
Sort the unvisited vertex list.
If all of the vertices are removed, and no path was found, then no path exists.