Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Applied Example of Dijkstra's Algorithm

No description
by

Daniel Truong

on 30 December 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Applied Example of Dijkstra's Algorithm

Applied Example of Dijkstra's Algorithm
Say we want to deliver a package from Astana, Kazakhstan...
...to Vancouver, British Columbia...
...via air delivery.
However, the delivery plane can only travel up to 8,000 kilometers before needing a refuel...
...and we want to cut down on the total distance traveled so as to save on fuel expenses.
What is Dijkstra's Algorithm?
What would we be using this for?
Dijkstra's Algorithm is a graph search algorithm published in 1959. It was initially conceived of in 1956 by Dutch computer scientist Edsger Dijkstra. The objective of the algorithm is to find the shortest path from one source to another.
Dijkstra's algorithm has multiple applications in real life; mainly in computer networking or commercial shipping. We use this algorithm when the objective is to go from Point A (source) to Point B (sink), but there are multiple stops along the way. Each stop is represented as a vertex and paths to each vertices are represented as edges of a specific length.
For an applied example...
What can we do?
We have fueling stations in:
Moscow, Russia
London, England
Barcelona, Spain
Algiers, Algeria
San Juan, Puerto Rico
Boston, Massachusetts
Houston, Texas
Helena Montana
Beijing, China
Delhi, India
Tokyo, Japan
Singapore
Brisbane, Australia
Honolulu, Hawaii
Anchorage, Alaska
San Francisco, California
We can start by representing Astana as the source of the graph, Vancouver as the sink. Each refueling station will be vertices (nodes) in between the source and the sink. The edges will represent the distance, in kilometers, between each station.
We have calculated all possible paths from Astana to Vancouver. If we are to minimize on distance traveled, we would go...
...From Astana, Kazakhstan...
..To Moscow, Russia...
..To London, England...
..To Boston, Massachusetts...
...and finally to Vancouver.

The total journey would require approximately 13,934 kilometers to travel.
In conclusion, we can use Dijkstra's algorithm for a number of applied, real life situations. Amongst them, finding the shortest distance to travel from point A to B.
Prezi presentation by Dan Truong
We represent each node as having been unvisited. The source node, Astana, is at a distance of 0 because it is our first node.
We calculate the distance it takes to go from the source to the next node(s).
Because each child node (from the source)
has only one source node, we mark the total
distance with an asterisk and we move on and calculate the total distances for the next generation of nodes.
Likewise with the last step, we mark an asterisk to nodes that have only a single previous destination.
Now we make note of the Singapore node. There are two paths that lead to Singapore: Beijing and Delhi. We calculate the total distance it takes to go from either Beijing or Delhi.
From Beijing to Singapore: 8917 km
From Delhi to Singapore: 8266 km
Because the distance from Delhi to Singapore is shorter, we record this distance and mark it with an asterisk as the assumed path to take.
We further continue calculating the total distances amongst further nodes.
Now we make note of the Honolulu node. There are two paths that lead to Honolulu: Brisbane and Tokyo. We calculate the total distance it takes to go from either Brisbane or Tokyo.
From Brisbane to Honolulu: 21984 km
From Tokyo to Honolulu: 12468 km
Because the distance from Tokyo to Honolulu is shorter, we record this distance and mark it with an asterisk as the assumed path to take.
Now let us observe the Boston node. There are two paths that lead to Boston: London and Barcelona. We calculate the total distance it takes to go from either London or Barcelona.
From London to Boston: 9912 km
From Barcelona to Boston: 11017 km
Because the distance from London to Boston is shorter, we record this distance and mark it with an asterisk as the assumed path to take.
Now we further continue calculating the total distances amongst further nodes.
We now observe the Vancouver sink node. There are five paths that lead to Vancouver: Boston, Helena, Houston, Anchorage and San Francisco. These are the distances calculated:
From Boston to Vancouver: 13934 km
From Helena to Vancouver: 18575 km
From Houston to Vancouver: 18863 km
From Anchorage to Vancouver: 13957 km
From San Francisco to Vancouver: 17595 km
Because the distance from Boston to Vancouver is shorter, we record this distance and mark it with an asterisk as the assumed path to take.
Full transcript