A Bit About Dijkstra’s

Challenges

  1. (Easy) Identify a correct graph on which you can run this algorithm. Run the algorithm and verify your answers with one of the applications quoted above.
  2. (Easy) Read up about A* Algorithm.
  3. (Medium) Program Dijkstra’s Algorithm in any of your favourite programming language. Get in touch with me, if you need help.
  4. (Medium) Once you implement Dijkstra’s Algorithm in any languages, use it to make a navigation system for your locality. You will have to see how to convert the road network into a graph – what will be vertices and what will be edges and what factors will you use to determine edge weights etc.
  5. (Hard) Identify any other real-life problems you can solve with Dijkstra’s Algorithm, that you come across in your personal life.
  6. (Hard) We know that there may be many shortest-paths from s to some vertex. Dijkstra’s will find only one of them. Give an example of graph, which has more than one shortest-path between start vertex and end vertex.

Pages: Contents<< Previous 11 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.