Dijkstra’s algorithm

From Computer Science Wiki
Jump to: navigation, search

Exclamation.png This is student work which has not yet been approved as correct by the instructor

Case studyDevote time and attention to gaining knowledge of (an academic subject), especially by means of books notes[1]

Introduction

The algorithm was conceived by Edsger Dijkstra in 1956. It is a path finding algorithm that is used to find the shortest path between points on a grid. It is often used in GPSs to help drivers find their way.

[2]

How does it work or a deeper look

“For a given source node in the graph, the algorithm finds the shortest path between that node and every other.It can also be used for finding the shortest paths from a single node to a single destination node by stopping the algorithm once the shortest path to the destination node has been determined. 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, Dijkstra's algorithm can be used to find the shortest route between one city and all other cities.”

Examples

When you are meeting friends at a restaurant downtown and you use a gps app, the app uses Dijkstra’s Algorithm to test all available routes. Then it chooses the one that would be the quickest and easiest for you to take.

Pictures, diagrams

Pictures and diagrams go a LONG way to helping someone understand a topic. Especially if your topic is a little abstract or complex. Using a picture or diagram is a two part process:

  1. upload a file
  2. use the file on a wiki page

External links

  • It would be helpful
  • to include many links
  • to other internet resources
  • to help fellow students
  • Please make sure the content is good
  • and don't link to a google search results, please

References