**Dijkstra's algorithm**:

Dijkstra's algorithm for shortest path can be used to find the shortest path from the source vertex to

*any one vertex*or

*all of the vertices*of the graph. It is a good example for dynamic programming where the shortest path from source vertex to the optimized vertices (not in unoptimized set Q) is calculated and the process continues till all vertices are optimized (or target vertex is optimized).

Below is the pseudocode for Dijkstra's algorithm from wiki. min[] (minimum distance from source to optimized vertices) and previous[] (previous vertex with minimum distance) are maintained. Initially all vertices are in Q, min[source] is 0 and other min values are infinity, previous[] for all vertices is undefined. A vertex x in Q with smallest min[] is chosen by using priority queue or heap (with log|V| time). For all neighbors n of x where n in Q, we update the existing min distance to n (

`min[n]`

) if we can get to n **through x**with smaller distance (

`min[x] + dist_between(x, n)`

) and also previous[n] as x.```
function Dijkstra(Graph, source):
for each vertex v in Graph:
min[v] = infinity
previous[v] = undefined
min[source] = 0
Q = the set of all nodes in Graph // unoptimized nodes in Q
while Q is not empty:
x = node in Q with smallest min[x]
remove x from Q
for each neighbor n of x and n not removed from Q:
min_x_n = min[x] + dist_between(x, n)
if min_x_n < min[n]:
min[n] = min_x_n
previous[n] = x
return previous[]
```

If we know the target vertex, we can break out of the while loop when target is the node removed from Q with smallest min (at the start of the while loop). If we exhaust all the nodes (till Q is empty), then we get the minimum distance for all the nodes

**from source**.

**Dijkstra's algorithm with limit**:

Another variation of the problem is to enforce a limit or range value. Then we maintain another array left[] for each vertex to specify the value remaining so far after that vertex is traversed (left[n] = limit - min[n] or

**left[n] = left[x] - dist_between(x, n)**

). We initialize it to 0 for all vertices and left[source] = limit. We check if **left[x] - ****dist_between(x, n) >= 0**

before updating the min[n] and previous[n] and also update left[n] i.e. *we only update distance or costs if they are within the limit or range*. If limit if greater than the shortest paths to targets, the process is the same. If limit if lesser, then we get an x with

**min[x] = infinity**

and quit the process with no path.
```
function Dijkstra(Graph, source, limit):
for each vertex v in Graph:
min[v] = infinity
previous[v] = undefined
min[source] = 0
Q = set of all nodes in Graph // unoptimized nodes
while Q is not empty:
x = node in Q with smallest min[]
if x == undefined: // all min[x] is infinity
return null // no path exists
remove x from Q
for each neighbor n of x and n not removed from Q:
min_x_n = min[x] + dist_between(x, n)
if min_x_n < min[n] && min_x_n <= limit:
min[n] = min_x_n
previous[n] = x
return previous[]
```

*This behaves similar to the A* algorithm where left[x]*

__acts__as the heuristic_cost(x) function and min[x] as the actual_cost(x) function. The difference in A* and*Dijkstra*

*with limit is that -*

*heuristic_cost(x) is an estimated function, instead of limit - min[x] and*

*x picked from Q is the node with smallest heuristic_cost(x) + actual_cost(x), instead of smallest*

*actual_cost(x)*

*. Thus, the original Dijkstra's algorithm without the limit is a special case of A* algorithm where the*

*heuristic_cost(x) is 0.*

By enforcing a limit, all the vertices of the graph are not explored. This is particularly useful when there are a lot of vertices in the graph (ex: maps).

If we use a binary heap for extracting the minimum node from Q, then

**the algorithm takes**

*I think***O(|E|+|V|log |V|)**(

*O((|*

*E|+|*

*V|) log |*

*V|) according to wiki*). It takes O(|V|) for

`while`

loop, O(log|V|) for extracting smallest min from binary heap and **only**O(|E|) for the

`for each`

loop.
## No comments:

## Post a Comment