Shortest Path: Dijkstra

Dijkstra Algorithm

Dijkstra's algorithm finds the shortest path between any two graph vertices. It differs from the minimum spanning tree in that the shortest distance between two vertices may not include all of the graph's vertices. Djikstra used this property in the opposite direction, i.e. we overestimated the distance of each vertex from the starting vertex. Then we visit each node and its neighbours to find the shortest subpath between them. The algorithm takes a greedy approach in that it seeks the next best solution in the hope that the result is the best solution for the entire problem.

function dijkstra(G, S)

    for each vertex V in G
        distance[V] <- infinite
        previous[V] <- NULL
        If V != S, add V to Priority Queue Q
    distance[S] <- 0
     while Q IS NOT EMPTY
        U <- Extract MIN from Q
        for each unvisited neighbour V of U
            tempDistance <- distance[U] + edge_weight(U, V)
            if tempDistance < distance[V]
                distance[V] <- tempDistance
                previous[V] <- U
    return distance[], previous[]

We will apply relaxation to solve this shortest-path problem.

if(d[u]+ c(u, v)< d[v]){
 		d[v] = d[u] + c(u, v)
}

The time complexity of this algorithm depends on how many vertices this algorithm should be relaxed.

if n is a number of vertex then T(n) = n * n =n^2. O(n^2)

Solution:

Shortest path from node 1 to 6 is 1 -> 2 -> 3 -> 5 -> 4 -> 6

and the cost is 9.

Let's do it in tabular form

Shortest path from node 1 to 6 is 1 -> 2 -> 3 -> 5 -> 4 -> 6

and the cost is 9.

Applications of Dijkstra's Algorithm

• To determine the shortest path.
• In social networking software
• In a telecommunications network
• To locate the locations on the map