Skip to content

Modified Dijkstra algorithm for Graph Cycles(Polygon) generation on a undirected graph

christophermoverton edited this page Apr 25, 2015 · 2 revisions

The modified Dijkstra algorithm for the cycles(polygon) generation in a undirected graph is fairly straightforward. The algorithm forms a direction testing basis, where in the case that I've have constructed, constructing a minimally spanning path in a counter clockwise orientation relative to the source target node pair. To do this, for instance, I would always choose a source node coordinate ordered in Cartesian plane relative the target node where in this case the source y position is always less than the target y, and likewise, also attempting to pick a x minimal neighbor node for all neighboring nodes greater than source y. Next I create an exclusion set of all other nodes relative source and target that have positions less than source and target x positions, and further excluding nodes in max(source x, target x) for nodes greater than target y. In this case constraints in path tracing are then shown by a diagram illustration below.