**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.