Use your knowledge of searching graphs to find the shortest distance between two vertices on a graph!

Dijkstra's Algorithm: Conceptual

How efficient is Dijkstra’s algorithm? Let’s break it into different parts: 
- Searching through the graph
- Keeping track of distances

Just like breadth-first search and depth-first search, to search through an entire graph, in the worst case, we would go through all of the edges and all of the vertices resulting in a runtime of O(E + V).

For Dijkstra's, we use a min-heap to keep track of all the distances. Searching through and updating a min-heap with V nodes takes O(log V) because in each layer of the min-heap, we reduce the number of nodes we are looking at by a factor of 2.

![Min-Heap](https://content.codecademy.com/programs/cs-path/dijkstra's%20conceptual/min%20heap)

In the worst case, we would update the min-heap every iteration. Since there are at most E + V iterations of Dijkstra’s and it takes log V to update a min-heap in the worst case, then the runtime of Dijkstra’s is **O((E+V)log V)**.



Diagram of the worst-case runtime of Djikstra's algorithm: O((V+E)*log(V))

Dijkstras Algorithm: Conceptual Runtime

Now that we know how to properly search a graph, how can we use these skills in real life?

One of the most common applications of graph searches is to find the shortest distance between vertices. Finding this distance has a variety of applications such as finding the optimal route to a destination or transferring data in a computer network. 

Take a look at the graph below. Finding the shortest path between vertex A and vertex E may seem easy in your brain, but telling a computer how to find it is a bit more complicated.

![Graph](https://content.codecademy.com/programs/cs-path/dijkstra's%20conceptual/graph%20example)

Fortunately, there is an algorithm that computes the shortest distance from a given vertex to the rest of the vertices in a graph. This is called **_Dijkstra’s Algorithm_**.

Dijkstra’s Algorithm works as following:
1. Instantiate a dictionary that will eventually map vertices to their distance from the start vertex
1. Assign the start vertex a distance of 0 in a min heap
1. Assign every other vertex a distance of infinity in a min heap
1. Remove the vertex with the smallest distance from the min heap and set that to the current vertex
1. For the current vertex, consider all of its adjacent vertices and calculate the distance to them as **(distance to the current vertex) + (edge weight of current vertex to adjacent vertex)**. 
1. If this new distance is less than the current distance, replace the current distance.
1. Repeat 4 and 5 until the heap is empty
1. After the heap is empty, return the distances


That may seem confusing! Be sure to check out the video in order to better visualize this algorithm.


Intro to Dijkstra's Algorithm: Conceptual

Congratulations on grasping a conceptual understanding of Dijkstra’s Algorithm! 

Here’s a quick recap of what you've learned:
- Dijkstra’s algorithm is an algorithm to find all of the shortest distances between a start vertex and the rest of the vertices in a graph.
- The algorithm works by keeping track of all the distances and updating the distances as it conducts a breadth-first search.
- Dijkstra’s algorithm runs in O((E+V)log V).
