A variant of Dijkstra's algorithm for finding a shortest s-t path in an Euclidean graph (edge weights correspond to Euclidean distance between vertices). Terminates early, as soon as a shortest s-t path has been found and only visits a small part of the graph. Similar ideas are used in A*-type algorithms.
Finding a path can be accelerated by searching from start and destination simultaneously.
This algorithm considers vertices as points in 2-dimensional space and implicitly assumes the existence of all edges in the complete graph. Furthermore, edge weights are Euclidean. It finds a matching of minimal weight. The matching is perfect if the number of vertices is even