A Bit About Dijkstra’s


Question on Quora discussing the same.

A* Algorithm, an algorithm to find shortest-path weight from single source to single destination is an extension of Dijkstra’s algorithm and is widely used in developing navigation apps like Google Maps.

It is also used as a “subroutine” (like “INITIALIZE-SINGLE-SOURCE” and “RELAX” algorithm here in many other algorithms like Johnson’s algorithm, which is introduced in Chapter 25 of Introduction to Algorithms by CLRS.

For example, if the nodes of the graph represent cities and edge path costs represent driving distances between pairs of cities connected by a direct road (for simplicity, ignore red lights, stop signs, toll roads and other obstructions), Dijkstra’s algorithm can be used to find the shortest route between one city and all other cities. A widely used application of shortest path algorithm is network routing protocols, most notably IS-IS (Intermediate System to Intermediate System) and Open Shortest Path First (OSPF).

– Wikipedia

Pages: Contents<< Previous 9 Next Page>>

One Comment Add yours

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.