Dijkstra's Algorithm

Wednesday, 24 April 2019

10:26 AM

In a weighted graph , the weight of a path is the sum of all edge weights in that path.

 

Suppose we fix a vertex . A minimal -spanning tree is a special spanning tree. Like all spanning trees there is a unique path from  to any other vertex. But in the special thing in this tree is that each of these paths is the shortest. The procedure to construct a minimal -spanning tree is called Dijkstra's Algorithm:

 

1. Start by defining a tree

which contains only the vertex , i.e.  and

 

2. Consider all edges with one vertex in  and the other vertex not in

 

.

 

3. Find the edge  which minimises the sum

 

4. Add  to  and add  to

 

5. Repeat.

 

When constructed in this way,  will be a minimal -spanning tree.

 

---

 

:TLDR: start at a point, and find the shortest path from a node