# Applications of Dijkstra Algorithm

Dijkstra algorithm is a graph search algorithm that solves the problem of finding the shortest path from a point in a graph to a destination. It turns out that one can find the shortest paths from a given source to *all* points in a graph at the same time, hence this problem is sometimes called the single-source shortest paths problem. Dijkstra’s algorithm, was first conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959 and hence it is named after him.

### Finding the Shortest Path

There will also be no cycles as a cycle would define more than one path from the selected vertex to at least one other vertex. For a graph, **G** = **(V,E)**

**V**is a set of vertices and**E**is a set of edges

Dijkstra’s algorithm keeps two sets of vertices:

**S = **the set of vertices whose shortest paths from the source have already been determined *and*

**V-S = **the remaining vertices

The other data structures needed are:

**d =** array of best estimates of shortest path to each vertex

**pi = **an array of predecessors for each vertex

The basic mode of operation is:

- Initialize
**d**and**pi**, - Set
**S**to empty, - While there are still vertices in
**V-S**, - Sort the vertices in
**V-S**according to the current best estimate of their distance from the source, - Add
**u**, the closest vertex in**V-S**, to**S**, - Relax all the vertices still in
**V-S**connected to**u**

As the algorithm goes on and sees more and more vertices, it attempts to update d[v] for each vertex in the graph. The process of updating estimates is called *relaxation.* The worst-case running time for the Dijkstra algorithm on a graph with n nodes and m edges is O(n2) because it allows for directed cycles. It even finds the shortest paths from a source node s to all other nodes in the graph. This is basically O(n2)for node selection and O(m)for distance updates. While O(n2) is the best possible complexity for dense graphs, the complexity can be improved significantly for sparse graphs.

### Example

**we have to find the shortest path from A to F**.

Node |
Distance from A |

B | 15 |

C | 5 |

D | N/A |

E | N/A |

F | N/A |

G | N/A |

H | N/A |

Node |
Distance from A |

B | 15 |

C | 5 |

D | 15+15=30 |

E | 5+5=10 |

F | N/A |

G | N/A |

H | N/A |

Node |
Distance from A |

B | 15 |

C | 5 |

D | 15+15=30 |

E | 5+5=10 |

F | N/A |

G | 10+20=30 |

H | N/A |

Node |
Distance from A |

B | 15 |

C | 5 |

D | 15+15=30 |

E | 5+5=10 |

F | N/A |

G | 10+20=30 |

H | 30+5=35 |

Node |
Shortest Distance from A |

B | 15 |

C | 5 |

D | 15+15=30 |

E | 5+5=10 |

F | N/A |

G | 10+20=30 |

H | 35 |

### C++ Implementation of Dijkstra

C++ program to solve the single source shortest path problem using Dijkstra algorithm.

#include<iostream> #include<conio.h> #include<stdio.h> using namespace std; int shortest(int ,int); int cost[10][10],dist[20],i,j,n,k,m,S[20],v,totcost,path[20],p; main() { int c; cout <<"enter no of vertices"; cin >> n; cout <<"enter no of edges"; cin >>m; cout <<"\nenter\nEDGE Cost\n"; for(k=1;k<=m;k++) { cin >> i >> j >>c; cost[i][j]=c; } for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(cost[i][j]==0) cost[i][j]=31999; cout <<"enter initial vertex"; cin >>v; cout << v<<"\n"; shortest(v,n); } int shortest(int v,int n) { int min; for(i=1;i<=n;i++) { S[i]=0; dist[i]=cost[v][i]; } path[++p]=v; S[v]=1; dist[v]=0; for(i=2;i<=n-1;i++) { k=-1; min=31999; for(j=1;j<=n;j++) { if(dist[j]<min && S[j]!=1) { min=dist[j]; k=j; } } if(cost[v][k]<=dist[k]) p=1; path[++p]=k; for(j=1;j<=p;j++) cout<<path[j]; cout <<"\n"; //cout <<k; S[k]=1; for(j=1;j<=n;j++) if(cost[k][j]!=31999 && dist[j]>=dist[k]+cost[k][j] && S[j]!=1) dist[j]=dist[k]+cost[k][j]; } }

### Related Posts

- This Pointer, Static Members and destructors in C++
- All pairs Shortest Path (APSP) Floyd Warshall C++ Source Code
- Graphical Path Finding System using Dijkstra Algorithm
- Implementing Dijkstra Algorithm using Priority Queue (Heap) in C++
- Introduction to Graph data structure
- Graph search in C++
- Boyer-Moore String Searching Algorithm
- TIC TAC TOE Game in C++
- KMP string matching algorithm implemented in C++
- Finding Longest Common Subsequence in two String using C++
- Graph Implementation in C++
- Applications of Circular Linked List in Data Structures

### One Response to *Applications of Dijkstra Algorithm*

### Leave a Reply Cancel reply

### Popular Posts (last 30 days)

- Attendance Management Sys… 1203 view(s)
- Implementing Stack Data S… 596 view(s)
- Graph Implementation in C… 594 view(s)
- Applications of Stack in … 536 view(s)
- Circular Linked Lists 526 view(s)
- Simple Currency Converter… 444 view(s)
- GRASP Design Patterns 330 view(s)
- Advanced Data Structures … 268 view(s)
- C++ Tutorial for Intermed… 260 view(s)
- Sockets and Network Progr… 187 view(s)

### Related Links

### Tags

Android C-Sharp C/C++ language Classes Data structures Design Pattern Eclipse Game Development Graphics Design Books HTML iPhone JAVA JAVA GUI MIPS Assembly Mobile Programming Books Object Oriented PDF PHP Programming Programming Books Programming Languages Books Python RaphaelJS REST Source Code Threads Tutorial Web Development Books

what should i put in the edges cost?