Dijkstra's Algorithm Assignment Help

1. Dijkstra's Algorithm Introduction

Dijkstra’s algorithm was introduced by Dutch computer scientist Edsger W. Dijkstra in 1956. It is an iterative algorithm for finding shortest path between nodes in a data structure called graph. Graph data structure consists of a finite set of nodes and edges. The objective of introducing this algorithm was to determine the capabilities of then developed computer “ARMAC”. Since, graph can also be represented as road networks. So, Dijkstra in 1956 designed this shortest path algorithm and implemented it for ARMAC for transportation map of 64 cities in Netherland.

1.1 Implementing Dijkstra’s algorithm for different cases.

1. To find the shortest path between two nodes.
2. To find the shortest path between a single node taken as source node and find shortest path from this node to all other nodes in graph. Thus, behaving like a shortest path tree where the source node of graph will act as its root node. Thus, it can also be used for finding shortest route between one city and all other cities.
3. This algorithm can also be used to find the shortest path from a source node to a single destination node. This can be achieved by stopping the algorithm once we know the path for desired set of nodes.
4. Johnson’s algorithm uses Dijkstra’s algorithm as a subroutine.

2. Pre-requisites

The following conditions should be fulfilled before applying Dijkstra’s algorithm:

• All the edges must have non-negative weights.
• The graph can be of any type either directed or non-directed.
• The graph must be connected.

The steps for executing Dijkstra’s algorithm are as follows:

1. Create a list for unvisited nodes.
2. Choose a node as source node. Assign maximum possible cost, let’s say infinity to all other nodes.
3. Cost for source node will be zero, because we are considering the cost for each node from the source node.
4. Minimize the cost for each node. It will take multiple steps to minimize the cost. And for that follow the steps written below:
   • Calculate the new cost for each of the unvisited neighbours of the current node from that node.
   • Let’s take an example to show the calculation of minimum cost. For node 2 as the current node, the cost will be calculated as the minimum of the two cost ( (existing cost of node 2 or (sum of cost of node 1+ the cost of edge from node 1 to node 2))
5. If all the neighbours of the current node are taken into account. Then, the current node will be marked as visited and then removed from the list of unvisited nodes.
6. Then, choose another node from that list and repeat step 4.
7. If there is no possibility of improving the cost for any node. Then, we’ll stop.

3. Pseudocode

To make the implementation easy, we’ll take the Priority Queues for storing unvisited node. This will make the extraction of the node on the basis of minimum cost easy.

dijkstra(G, S)
dist[source] <- 0
previous[source] <- NULL
for each node N in G
if N != S
dist[N] <- infinite
previous[N] <- NULL
ADD V to Q
while Q IS NOT EMPTY
U <- Extract MIN from Q
for each unvisited neighbour V of U
tempDist <- dist[U] + edge_weight(U, V)
if tempDist < dist[V]
dist[V] <- tempDist
previous[V] <- U
return dist[], previous[]

4. Implementation in Java

The program given below is for adjacency matrix representation of the graph

import java.util.*;
import java.lang.*;
import java.io.*;

class Dijkstra
{
static final int N=9;
// list will contain the set of unvisited nodes
// this function will return the node with minimum distance value
int minVal(int dist[], Boolean list[])
{
int min = Integer.MAX_VALUE;
int min_index=-1;

for (int i= 0; i < V; i++)
if (list[i] == false && dist[i] <= min)
{
min = dist[i];
min_index = i;
}
return min_index;
}
// print distance array
void print(int dist[], int n)
{
System.out.println("Distance from source");
for (int j = 0; j< N; j++)
System.out.println(j+" \t\t "+dist[j]);
}
void dijkstra(int graph[][], int src)
{
//dist[i] will hold the distance from src to i
int dist[] = new int[N];
// list[i] will be true when the minimum distance will be achieved
Boolean list[] = new Boolean[N];

for (int i = 0; i < N; i++)
{
dist[i] = Integer.MAX_VALUE;
list[i] = false;
}
dist[src] = 0;
for (int c = 0; c < N-1; c++)
{
// node of minimum distance value will be selected to be as a source.
int u = minVal(dist, list);

list[u] = true;

// Update dist value of the adjacent nodes of the current node

for (int v = 0; v < N; v++)

if (!list[v] && graph[u][v]!=0 &&
dist[u] != Integer.MAX_VALUE &&
dist[u]+graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}

// print the constructed distance array
print(dist, N);
}
public static void main (String[] args)
{
// create the example graph
int graph[][] = new int[][]{
{0, 4, 0, 0, 0, 0, 0, 8, 0},
{4, 0, 8, 0, 0, 0, 0, 11, 0},
{0, 8, 0, 7, 0, 4, 0, 0, 2},
{0, 0, 7, 0, 9, 14, 0, 0, 0},
{0, 0, 0, 9, 0, 10, 0, 0, 0},
{0, 0, 4, 14, 10, 0, 2, 0, 0},
{0, 0, 0, 0, 0, 2, 0, 1, 6},
{8, 11, 0, 0, 0, 0, 1, 0, 7},
{0, 0, 2, 0, 0, 0, 6, 7, 0}
};
ShortestPath s= new ShortestPath();
s.dijkstra(graph, 0);
}
}

5. Implementation in C

The program given below is for adjacency matrix representation of the graph

#include < stdio.h>
#include < limits.h>

// total nodes in the graph
#define N 9
// list will contain the set of unvisited nodes
// this function will return the node with minimum distance value
int minDistance(int dist[], bool list[])
{
int min = INT_MAX;
int min_index;

for (int i = 0; i < N; i++)
if (list[i] == false && dist[i] <= min)
min = dist[i];
min_index = v;

return min_index;
}
// print distance array
int print(int dist[], int n)
{
int i=0;
printf("Distance of node from source\n");
for (i = 0; i < N; i++)
printf("%d \t\t %d\n", i, dist[i]);
}

void dijkstra(int graph[N][N], int src)
{
int i, j, count;
int dist[N]; //dist[i] will hold the distance from src to i

bool list[N]; // list[i] will be true when the minimum distance will be achieved

// Initialize all distances as INFINITE and list[] as false
for ( i = 0; i < N; i++)
dist[i] = INT_MAX;
list[i] = false;
dist[src] = 0;

// Find shortest path for all nodes
for ( count = 0; count < V-1; count++)
{
// node of minimum distance value will be selected to be as a source
int u = minDistance(dist, list);

// Mark the picked node as unvisited
list[u] = true;

// Update dist value of the adjacent vertices of the picked vertex.
for (j = 0; j< N; j++)
if (!list [j] && graph[u][j] && dist[j] != INT_MAX && dist[u]+graph[u][j] < dist[j])
dist[j] = dist[u] + graph[u][j];
}

// print the constructed distance array
print(dist, N);
}
int main()
{
// create the example graph
int graph[V][V] = {
{0, 4, 0, 0, 0, 0, 0, 8, 0},
{4, 0, 8, 0, 0, 0, 0, 11, 0},
{0, 8, 0, 7, 0, 4, 0, 0, 2},
{0, 0, 7, 0, 9, 14, 0, 0, 0},
{0, 0, 0, 9, 0, 10, 0, 0, 0},
{0, 0, 4, 14, 10, 0, 2, 0, 0},
{0, 0, 0, 0, 0, 2, 0, 1, 6},
{8, 11, 0, 0, 0, 0, 1, 0, 7},
{0, 0, 2, 0, 0, 0, 6, 7, 0}
};
dijkstra(graph, 0);
return 0;
}

Analysis of Dijkstra’s Algorithm

The list which we used for storing unvisited node, with different implementations produces different time complexity.

List as a linear array : If there are N nodes then, min_distance function takes O(N) time and number of operations is |N|. Therefore, in this function, it will take O(N^2) time.

The total number of edges let’s assume is E. That means for loop will iterate |E| times. Hence, the running time of this algorithm using linear array implementation is O(N² + E) = O(N²).

List as a binary heap: If there are N number of operations and to build a binary heap. It will take O(N) time. Then, min_distance function will take O(log N) time.

If the number of edges is |E| and the graph is sparse. Then the total running time with binary heap implementation is O(E log N).

List as a Fibonacci heap:

Fibonacci heap is the more complicated version of priority queue implementation. It implements increase_priority in O(1) time. If the number of edges is |E| and there are N number of nodes.

Find the best Dijkstra's Algorithm Assignment Help Services with us

Try our determination care now, solution of your problem is righteous a depression departed. Knock any quantify at our 24x7 live supports for any ask. To know about how to proceed, just visit how it Works page at Assignmenthelp.net.

To schedule a Dijkstra's Algorithm tutoring session Live chat

To submit Dijkstra's Algorithm Assignments Click here

The Assignment Help Services that we provide include: Dijkstra's Algorithm, Data Structure, Trees Assignment Help, Dijkstra's Algorithm Project Help and Dijkstra's Algorithm Tutorials.

So, the time complexity of Dijkstra’s algorithm with Fibonacci heap implementation will be O(N log N+ E).

When there are large constant factors involved. Then, in that case, the Fibonacci heap implementation becomes impractical.