# Dijkstra’s algorithm

**Dijkstra's** algorithm is way of finding **shortest path** from a **source** vertex to** sink** in a given **connected** and **weighted** graph. It is somewhat similar to Prim's algorithm and it works for **directed** as well as **undirected** graphs. The step by step process is specified below :

**Source vertex**is chosen and**marked**.- Mark distances at all vertices as
**infinity**and at**source**vertex as**0**. - Update the distances of adjacent vertices from
**infinity**by given**distances**on the**graph**. - We look for
**minimum**distance value from source vertex to adjacent vertices. - The
**minimum distance**is chosen and next vertex is**marked**. - Look for the adjacent vertices of
**marked**vertex. - Replace the distance if it is less than the mentioned value at the vertices.
- Keep on following the same procedure until shortest path to sink is obtained.

**Example:**

Consider a **weighted** and **undirected** graph as shown in Fig 1

- Choose a
**source vertex**.In Fig 2 ,**a**is chosen as the**source**vertex. **Mark**all the distances at vertices as**infinity**initially and distance of source vertex as**0**

- Look for
**neighbors**of source vertex a.(Fig 3). **b**and**i**are the**adjacent**vertices.- Update the
**distance**at**b**from infinity to**4**and at**i**to**8**. - Find the minimum distance from
**a**. **4**is smaller than**8**so**b**is the next**marked**vertex.

- Look for the
**neighbors**of b. **c**and**i**are the**adjacent**vertices.- Update value at
**c**from infinity to**12(4+8)**as distance from source to**c**is**12**.(Fig 4) - Distance from
**a**to**i**through**b**is**15**(11+4) and a to**i**directly is**8.**So**8**is not updated. - Look for next min distance to a vertex and do not count already marked vertices and edges.
- The distance at c is
**12**and at i is**8**,so**i**is marked.

- Look for neighbors of
**i**. - Update distance at
**h**to**15**(8+7) and at**g**to**9**. - Distance from source
**a**to**b**is**4**and**a**to**b**through**i**is**19**so it is not updated. - Look for next minimum distance from marked vertices.
**12,15,9**are the respective distances from marked vertices.- Mark vertex
**g**and**Edge(i,g)**as**9**is the minimum distance from source**a**to**g**through**i.**

- Look for neighbors of
**g**. - The distance at
**h**from a through**i**is**15**and from**a**through**i**and**g**is again**15**so it is not updated(Fig 6). - The distance from
**a**to**f**through**i**and**g**is**11**.So update it by**11**.

- Look for the next minimum distance(Fig 7).
**12,15,11**are the distances from marked vertices.- Mark
**f**and**Edge(g,f)**as distance is minimum.

- Neighbors of f are
**c,d,e**. - Distance at
**c**is not required to be updated. - Update distance at
**d**to**25**(11+14) and**a**t**e**to**21**(11+10)(Fig 8). - Look for minimum distance.
**12,15,19,21**are the distances available for consideration.- Mark vertex
**c**as**12**is minimum.

- Distance of neighbors of
**c**is not required to be updated. - Mark
**d**and then**e**.(Fig 9)

The following table gives the details of dijkstra's algorithm applied on Fig 1.The shortest path from a to e is **{a,b,i,g,f,c,d,e}** with minimum cost of **21**.

## Comments

So empty here ... leave a comment!