Algorithms used by the ArcGIS Netwo

Algorithms used by the ArcGIS Network Analyst extension
The routing solvers within the ArcGIS Network Analyst extension—namely the Route, Closest Facility, and OD Cost Matrix solvers—are based on the well-known Dijkstra's algorithm for finding shortest paths. Each of these three solvers implements two types of path-finding algorithms. The first type is the exact shortest path, and the second is a hierarchical path solver for faster performance. The classic Dijkstra's algorithm solves a shortest-path problem on an undirected, nonnegative, weighted graph. To use it within the context of real-world transportation data, this algorithm is modified to respect user settings such as one-way restrictions, turn restrictions, junction impedance, barriers, and side-of-street constraints while minimizing a user-specified cost attribute. The performance of Dijkstra's algorithm is further improved by using better data structures such as d-heaps. In addition, the algorithm needs to be able to model the locations anywhere along an edge, not just on junctions.