What is Dijkstra’s Algorithm ?

Introduction

•  Dijkstra’s Algorithm was derived by a Dutch

• Computer Scientist ‘Edsger Dijkstra’ in 1956 and published in 1959.

• It’s a graph search algorithms that solve the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree.

• This algorithm is often used in routing and as subroutine in other graph algorithms.

How its work 

• This algorithm finds the path with lowest cost

(i.e. the short path) between the vertex and every other vertex. 

For example:

If the vertices Of the graph represent cities and edge path costs represent driving distance between pairs of cities connected by a direct road, Dijkstra can be used to find the short road between one city to all other cities.

• According to this algorithm to solve a given problem, we need to solve different part of problems.

Shortest Path

Negative Cost Edges:

1  Dijkstra’s algorithm assumes positive cost edges

2  For some applications, negative cost edges make sense

3  Shortest path not well defined if a graph has a negative cost cycle

 

1  Topological Sort can be used for solving the shortest path problem in directed a cyclic graphs

2  Bellman-Ford algorithm finds shortest paths in a graph with negative cost edges (or reports the existence of a negative cost cycle).

In some fields, artificial intelligence in particular, Dijkstra's algorithm or a variant of it is known as uniform cost search and formulated as an instance of the more general idea of best first search.

 Application of Dijkstra’s Algorithm

• Telephone Network

The vertices represents switching station, the edges represents transmission line, and the weight of edges represent the BW.

• Flight Agenda

To determine the earliest arrival time for the destination given an origin airport and start time.