Dijkstra’s shortest path algorithm
Dijkstra's shortest path algorithm is a well-known algorithm used in computer science to solve the shortest path problem for a weighted graph. It is named after its inventor, Edsger W. Dijkstra, a Dutch computer scientist.
The algorithm starts at a specified source node and explores the graph to find the shortest path from the source node to every other node in the graph. It maintains a set of visited nodes and a set of unvisited nodes. Initially, all nodes are unvisited, and the distance to every node from the source node is set to infinity. The algorithm then selects the unvisited node with the smallest distance from the source node and adds it to the visited set. It updates the distances of all the adjacent nodes to this newly added node, and continues this process until all nodes are visited or until the smallest distance from the source node to an unvisited node is infinity.
The algorithm guarantees that the distance to each node in the graph from the source node is the shortest possible distance. Additionally, the algorithm also computes the shortest path itself, not just the length of the path.
Dijkstra's algorithm is commonly used in various applications, such as finding the shortest path in transportation networks, routing in computer networks, and optimizing the allocation of resources in project management.
Here given code implementation process.
//C Program
//Dijkstra’s shortest path algorithm
#include <stdio.h>
#include <stdlib.h>
#include <limits.h> //for INT_MAX
#define INF INT_MAX
struct AjlistNode {
int id; //Vertices id
int weight;
struct AjlistNode *next;
};
struct Graph {
int data; //node key value
struct AjlistNode *next;
};
int size; //number of nodes
//set node key value
void set_data(struct Graph *node) {
if (node != NULL && size > 0) {
int index = 0;
for (index; index < size; index++) {
//set vertic node data
node[index].data = index; //set node key
//Initial no AjlistNode
//set NULL Value
node[index].next = NULL;
}
} else {
printf("Vertic Node is Empty");
}
}
void connect_edge(struct Graph *node, int V, int E, int weight) {
// create Adjacency node
struct AjlistNode *new_edge = (struct AjlistNode *) malloc(
sizeof(struct AjlistNode)
);
if (new_edge != NULL) {
new_edge->next = NULL;
new_edge->id = E;
new_edge->weight = weight;
struct AjlistNode *temp = node[V].next;
if (temp == NULL) {
node[V].next = new_edge;
} else {
while (temp->next != NULL) {
temp = temp->next;
}
new_edge->next = temp->next;
temp->next = new_edge;
}
} else {
printf("\n Memory overflow");
}
}
//Add Edge from Two given Nodes
void add_edge(struct Graph *node, int V, int E, int weight) {
//add edge form V to E
//V and E is Node location
if (V < size && E < size) {
connect_edge(node, V, E, weight);
if (V == E) {
return;
}
connect_edge(node, E, V, weight);
} else {
//not valid Vertices
printf("Invalid Node Vertices %d %d", V, E);
}
}
//Display Adjacency list of vertex
void print_graph(struct Graph *node)
{
if (node != NULL)
{
struct AjlistNode *temp = NULL;
for (int index = 0; index < size; index++) {
printf("\n Adjacency list of vertex %d :", index);
temp = node[index].next;
while (temp != NULL) {
//temp->id is graph node vertices
//in this case temp->id is same as
//node[temp->id].data
printf(" %d", node[temp->id].data);
temp = temp->next;
}
}
} else {
printf("Empty Graph");
}
}
int min_distance(int distance[], int visit[]) {
int position = -1;
for (int i = 0; i < size; ++i) {
if (visit[i] == 0) {
if (position == -1) {
position = i;
} else if (distance[position] > distance[i]) {
position = i;
}
}
}
return position;
}
void dijkstra_path(struct Graph *root, int source) {
if (root != NULL) {
int distance[size], visit[size], position = 0;
for (int i = 0; i < size; ++i) {
//Initial distance is infinity
distance[i] = INF;
visit[i] = 0;
}
distance[source] = 0;
struct AjlistNode *temp = NULL;
for (int i = 0; i < size; ++i) {
position = min_distance(distance, visit);
if (distance[position] != INF) {
temp = root[position].next;
while (temp != NULL) {
if (distance[position] + temp->weight < distance[temp->id]) {
distance[temp->id] = distance[position] + temp->weight;
}
temp = temp->next;
}
}
if (position != -1) {
visit[position] = 1;
}
}
printf("\nVertex Distance Source Node (%d)\n", source);
for (int i = 0; i < size; ++i) {
if (distance[i] == INF) {
printf(" %d \t \t INF\n", i);
} else {
printf(" %d \t \t %d\n", i, distance[i]);
}
}
} else {
printf("Empty Graph");
}
}
int main() {
size = 11;
struct Graph *node = NULL;
node = (struct Graph *) malloc(sizeof(struct Graph) *size);
if (node == NULL) {
printf("\n Memory overflow");
} else {
//First set node keys
set_data(node);
//Connected two node with Edges
add_edge(node, 0, 1, 5);
add_edge(node, 0, 2, 2);
add_edge(node, 0, 3, 4);
add_edge(node, 1, 2, 2);
add_edge(node, 1, 4, 6);
add_edge(node, 2, 3, 1);
add_edge(node, 2, 6, 2);
add_edge(node, 3, 6, 3);
add_edge(node, 4, 5, 7);
add_edge(node, 4, 7, 6);
add_edge(node, 5, 6, 3);
add_edge(node, 5, 7, 8);
add_edge(node, 5, 9, 7);
add_edge(node, 6, 8, 8);
add_edge(node, 6, 9, 4);
add_edge(node, 7, 10, 7);
add_edge(node, 8, 9, 2);
add_edge(node, 8, 10, 7);
add_edge(node, 9, 10, 8);
print_graph(node);
dijkstra_path(node, 0);
}
return 0;
}
Output
Adjacency list of vertex 0 : 1 2 3
Adjacency list of vertex 1 : 0 2 4
Adjacency list of vertex 2 : 0 1 3 6
Adjacency list of vertex 3 : 0 2 6
Adjacency list of vertex 4 : 1 5 7
Adjacency list of vertex 5 : 4 6 7 9
Adjacency list of vertex 6 : 2 3 5 8 9
Adjacency list of vertex 7 : 4 5 10
Adjacency list of vertex 8 : 6 9 10
Adjacency list of vertex 9 : 5 6 8 10
Adjacency list of vertex 10 : 7 8 9
Vertex Distance Source Node (0)
0 0
1 4
2 2
3 3
4 10
5 7
6 4
7 15
8 10
9 8
10 16//C++ Program
//Dijkstra’s shortest path algorithm
#include<iostream>
#include <limits.h> //for INT_MAX
using namespace std;
class AjlistNode {
public:
//Vertices node key
int id;
int weight;
AjlistNode *next;
AjlistNode(int id, int weight) {
//Set value of node key
this->id = id;
this->weight = weight;
this->next = NULL;
}
};
class Vertices {
public:
int data;
AjlistNode *next;
Vertices()
{
this->data = 0;
this->next = NULL;
}
Vertices(int data) {
this->data = data;
this->next = NULL;
}
};
class MyGraph {
public:
//number of Vertices
int size;
Vertices *node;
MyGraph(int size) {
//set value
this->size = size;
node = new Vertices[size];
this->set_data();
}
//Set initial node value
void set_data() {
if (node == NULL) {
cout << "\nEmpty Graph";
} else {
for (int index = 0; index < this->size; index++) {
node[index] = index;
}
}
}
//connect two nodes
void connect(int start, int last, int weight) {
AjlistNode *new_edge = new AjlistNode(last, weight);
if (node[start].next == NULL) {
node[start].next = new_edge;
} else {
AjlistNode *temp = node[start].next;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = new_edge;
}
}
//Add edge of two nodes
void add_edge(int start, int last, int weight) {
if (start >= 0 &&
start < this->size &&
last >= 0 &&
last < this->size &&
node != NULL) {
this->connect(start, last, weight);
if (start != last) {
this->connect(last, start, weight);
}
} else {
cout << "\nHere Something Wrong";
}
}
void print_graph() {
if (this->size > 0 &&
node != NULL) {
for (int index = 0; index < this->size; index++) {
cout << "\nAdjacency list of vertex " << index << " :";
AjlistNode *temp = node[index].next;
while (temp != NULL) {
cout << " " << node[temp->id].data;
temp = temp->next;
}
}
}
}
int min_distance(int *distance, int *visit) {
int position = -1;
for (int i = 0; i < this->size; ++i) {
if (visit[i] == 0) {
if (position == -1) {
position = i;
} else
if (distance[position] > distance[i]) {
position = i;
}
}
}
return position;
}
void dijkstra_path(int source) {
if (node != NULL) {
int *distance = new int[size];
int *visit = new int[size];
int position = 0;
int i = 0;
for (i = 0; i < this->size; ++i) {
distance[i] = INT_MAX;
visit[i] = 0;
}
distance[source] = 0;
AjlistNode *temp = NULL;
for (i = 0; i < this->size; ++i) {
position = this->min_distance(distance, visit);
if (distance[position] != INT_MAX) {
temp = node[position].next;
while (temp != NULL) {
if (distance[position] + temp->weight < distance[temp->id]) {
distance[temp->id] = distance[position] + temp->weight;
}
temp = temp->next;
}
}
if (position != -1) {
visit[position] = 1;
}
}
cout << "\nVertex Distance Source Node (" << source << ")\n";
for (i = 0; i < this->size; ++i) {
if (distance[i] == INT_MAX) {
cout << " " << i << " \t \t INF\n";
} else {
cout << " " << i << " \t \t " << distance[i] << "\n";
}
}
} else {
cout << "Empty Graph";
}
}
};
int main() {
//11 implies the number of nodes in graph
MyGraph g = MyGraph(11);
//Connected two node with Edges
//First two parameter indicates number start and end nodes
//And third parameter indicates weight of edge
g.add_edge(0, 1, 5);
g.add_edge(0, 2, 2);
g.add_edge(0, 3, 4);
g.add_edge(1, 2, 2);
g.add_edge(1, 4, 6);
g.add_edge(2, 3, 1);
g.add_edge(2, 6, 2);
g.add_edge(3, 6, 3);
g.add_edge(4, 5, 7);
g.add_edge(4, 7, 6);
g.add_edge(5, 6, 3);
g.add_edge(5, 7, 8);
g.add_edge(5, 9, 7);
g.add_edge(6, 8, 8);
g.add_edge(6, 9, 4);
g.add_edge(7, 10, 7);
g.add_edge(8, 9, 2);
g.add_edge(8, 10, 7);
g.add_edge(9, 10, 8);
g.print_graph();
//source node 0 by default
g.dijkstra_path(0);
return 0;
}
Output
Adjacency list of vertex 0 : 1 2 3
Adjacency list of vertex 1 : 0 2 4
Adjacency list of vertex 2 : 0 1 3 6
Adjacency list of vertex 3 : 0 2 6
Adjacency list of vertex 4 : 1 5 7
Adjacency list of vertex 5 : 4 6 7 9
Adjacency list of vertex 6 : 2 3 5 8 9
Adjacency list of vertex 7 : 4 5 10
Adjacency list of vertex 8 : 6 9 10
Adjacency list of vertex 9 : 5 6 8 10
Adjacency list of vertex 10 : 7 8 9
Vertex Distance Source Node (0)
0 0
1 4
2 2
3 3
4 10
5 7
6 4
7 15
8 10
9 8
10 16//Java Program
//Dijkstra’s shortest path algorithm
class AjlistNode {
//Vertices node key
public int id;
public int weight;
public AjlistNode next;
public AjlistNode(int id,int weight) {
//Set value of node key
this.id = id;
this.weight=weight;
this.next = null;
}
}
class Vertices {
public int data;
public AjlistNode next;
public Vertices(int data) {
this.data = data;
this.next = null;
}
}
public class MyGraph
{
//number of Vertices
public int size;
public Vertices node[];
public MyGraph(int size)
{
//set value
this.size = size;
node=new Vertices[size];
this.set_data();
}
//Set initial node value
public void set_data()
{
if(node == null)
{
System.out.println("\nEmpty Graph");
}else
{
for(int index=0;index<size;index++)
{
node[index]=new Vertices(index);
}
}
}
//connect two nodes
public void connect(int start,int last ,int weight)
{
AjlistNode new_edge=new AjlistNode(last,weight);
if(node[start].next==null)
{
node[start].next=new_edge;
}else
{
AjlistNode temp=node[start].next;
while(temp.next!=null)
{
temp=temp.next;
}
temp.next=new_edge;
}
}
//Add edge of two nodes
public void add_edge(int start,int last,int weight)
{
if(start>=0 && start < size && last >= 0 && last < size && node != null)
{
connect(start,last,weight);
if(start!=last)
{
connect(last,start,weight);
}
}else
{
System.out.println("\nHere Something Wrong");
}
}
public void print_graph()
{
if(size >0 && node!=null)
{
for(int index = 0; index < size; index++)
{
System.out.print("\nAdjacency list of vertex "+index+" :");
AjlistNode temp = node[index].next;
while(temp != null)
{
System.out.print(" "+node[temp.id].data);
temp=temp.next;
}
}
}
}
int min_distance(int []distance, int []visit) {
int position = -1;
for (int i = 0; i < size; ++i) {
if (visit[i] == 0) {
if (position == -1) {
position = i;
} else
if (distance[position] > distance[i]) {
position = i;
}
}
}
return position;
}
void dijkstra_path( int source) {
if (node != null) {
int []distance = new int[size];
int []visit= new int[size];
int position = 0;
int i = 0;
for ( i = 0; i < size; ++i) {
distance[i] = Integer.MAX_VALUE;
visit[i] = 0;
}
distance[source] = 0;
AjlistNode temp = null;
for (i = 0; i < size; ++i) {
position = min_distance(distance, visit);
if (distance[position] != Integer.MAX_VALUE) {
temp = node[position].next;
while (temp != null) {
if (distance[position] + temp.weight < distance[temp.id]) {
distance[temp.id] = distance[position] + temp.weight;
}
temp = temp.next;
}
}
if (position != -1) {
visit[position] = 1;
}
}
System.out.print("\nVertex Distance Source Node ("+source+")\n" );
for (i = 0; i < size; ++i) {
if (distance[i] == Integer.MAX_VALUE) {
System.out.print(" "+i+" \t \t INF\n");
} else {
System.out.print(" "+i+" \t \t "+distance[i]+"\n" );
}
}
} else {
System.out.print("Empty Graph");
}
}
public static void main(String[] args)
{
//11 implies the number of nodes in graph
MyGraph g=new MyGraph(11);
//Connected two node with Edges
//First two parameter indicates number start and end nodes
//And third parameter indicates weight of edge
g.add_edge( 0, 1, 5);
g.add_edge( 0, 2, 2);
g.add_edge( 0, 3, 4);
g.add_edge( 1, 2, 2);
g.add_edge( 1, 4, 6);
g.add_edge( 2, 3, 1);
g.add_edge( 2, 6, 2);
g.add_edge( 3, 6, 3);
g.add_edge( 4, 5, 7);
g.add_edge( 4, 7, 6);
g.add_edge( 5, 6, 3);
g.add_edge( 5, 7, 8);
g.add_edge( 5, 9, 7);
g.add_edge( 6, 8, 8);
g.add_edge( 6, 9, 4);
g.add_edge( 7, 10, 7);
g.add_edge( 8, 9, 2);
g.add_edge( 8, 10, 7);
g.add_edge( 9, 10, 8);
g.print_graph();
//source node 0 by default
g.dijkstra_path(0);
}
}
Output
Adjacency list of vertex 0 : 1 2 3
Adjacency list of vertex 1 : 0 2 4
Adjacency list of vertex 2 : 0 1 3 6
Adjacency list of vertex 3 : 0 2 6
Adjacency list of vertex 4 : 1 5 7
Adjacency list of vertex 5 : 4 6 7 9
Adjacency list of vertex 6 : 2 3 5 8 9
Adjacency list of vertex 7 : 4 5 10
Adjacency list of vertex 8 : 6 9 10
Adjacency list of vertex 9 : 5 6 8 10
Adjacency list of vertex 10 : 7 8 9
Vertex Distance Source Node (0)
0 0
1 4
2 2
3 3
4 10
5 7
6 4
7 15
8 10
9 8
10 16
//C# Program
//Dijkstra’s shortest path algorithm
using System;
public class AjlistNode {
//Vertices node key
public int id;
public int weight;
public AjlistNode next;
public AjlistNode(int id, int weight) {
//Set value of node key
this.id = id;
this.weight = weight;
this.next = null;
}
}
public class Vertices {
public int data;
public AjlistNode next;
public Vertices(int data) {
this.data = data;
this.next = null;
}
}
public class MyGraph {
//number of Vertices
public int size;
public Vertices[] node;
public MyGraph(int size) {
//set value
this.size = size;
this.node = new Vertices[size];
this.set_data();
}
//Set initial node value
public void set_data() {
if (node == null) {
Console.WriteLine("\nEmpty Graph");
} else {
for (int index = 0; index < size; index++) {
node[index] = new Vertices(index);
}
}
}
//connect two nodes
public void connect(int start, int last, int weight) {
AjlistNode new_edge = new AjlistNode(last, weight);
if (node[start].next == null) {
node[start].next = new_edge;
} else {
AjlistNode temp = node[start].next;
while (temp.next != null) {
temp = temp.next;
}
temp.next = new_edge;
}
}
//Add edge of two nodes
public void add_edge(int start, int last, int weight) {
if (start >= 0 &&
start < size &&
last >= 0 &&
last < size &&
node != null) {
connect(start, last, weight);
if (start != last) {
connect(last, start, weight);
}
} else {
Console.WriteLine("\nHere Something Wrong");
}
}
public void print_graph() {
if (size > 0 &&
node != null) {
for (int index = 0; index < size; index++) {
Console.Write("\nAdjacency list of vertex " + index + " :");
AjlistNode temp = node[index].next;
while (temp != null) {
Console.Write(" " + node[temp.id].data);
temp = temp.next;
}
}
}
}
int min_distance(int[] distance, int[] visit) {
int position = -1;
for (int i = 0; i < size; ++i) {
if (visit[i] == 0) {
if (position == -1) {
position = i;
} else
if (distance[position] > distance[i]) {
position = i;
}
}
}
return position;
}
void dijkstra_path(int source) {
if (node != null) {
int[] distance = new int[size];
int[] visit = new int[size];
int position = 0;
int i = 0;
for (i = 0; i < size; ++i) {
distance[i] = int.MaxValue;
visit[i] = 0;
}
distance[source] = 0;
AjlistNode temp = null;
for (i = 0; i < size; ++i) {
position = min_distance(distance, visit);
if (distance[position] != int.MaxValue) {
temp = node[position].next;
while (temp != null) {
if (distance[position] + temp.weight < distance[temp.id]) {
distance[temp.id] = distance[position] + temp.weight;
}
temp = temp.next;
}
}
if (position != -1) {
visit[position] = 1;
}
}
Console.Write("\nVertex Distance Source Node (" + source + ")\n");
for (i = 0; i < size; ++i) {
if (distance[i] == int.MaxValue) {
Console.Write(" " + i + " \t \t INF\n");
} else {
Console.Write(" " + i + " \t \t " + distance[i] + "\n");
}
}
} else {
Console.Write("Empty Graph");
}
}
public static void Main(String[] args) {
//11 implies the number of nodes in graph
MyGraph g = new MyGraph(11);
g.add_edge(0, 1, 5);
g.add_edge(0, 2, 2);
g.add_edge(0, 3, 4);
g.add_edge(1, 2, 2);
g.add_edge(1, 4, 6);
g.add_edge(2, 3, 1);
g.add_edge(2, 6, 2);
g.add_edge(3, 6, 3);
g.add_edge(4, 5, 7);
g.add_edge(4, 7, 6);
g.add_edge(5, 6, 3);
g.add_edge(5, 7, 8);
g.add_edge(5, 9, 7);
g.add_edge(6, 8, 8);
g.add_edge(6, 9, 4);
g.add_edge(7, 10, 7);
g.add_edge(8, 9, 2);
g.add_edge(8, 10, 7);
g.add_edge(9, 10, 8);
g.print_graph();
g.dijkstra_path(0);
}
}
Output
Adjacency list of vertex 0 : 1 2 3
Adjacency list of vertex 1 : 0 2 4
Adjacency list of vertex 2 : 0 1 3 6
Adjacency list of vertex 3 : 0 2 6
Adjacency list of vertex 4 : 1 5 7
Adjacency list of vertex 5 : 4 6 7 9
Adjacency list of vertex 6 : 2 3 5 8 9
Adjacency list of vertex 7 : 4 5 10
Adjacency list of vertex 8 : 6 9 10
Adjacency list of vertex 9 : 5 6 8 10
Adjacency list of vertex 10 : 7 8 9
Vertex Distance Source Node (0)
0 0
1 4
2 2
3 3
4 10
5 7
6 4
7 15
8 10
9 8
10 16<?php
//Php Program
//Dijkstra’s shortest path algorithm
class AjlistNode {
//Vertices node key
public $id;
public $weight;
public $next;
function __construct($id, $weight) {
//Set value of node key
$this->id = $id;
$this->weight = $weight;
$this->next = null;
}
}
class Vertices {
public $data;
public $next;
function __construct($data) {
$this->data = $data;
$this->next = null;
}
}
class MyGraph {
//number of Vertices
public $size;
public $node;
function __construct($size) {
//set value
$this->size = $size;
$this->node = array_fill(0, $size, null);
$this->set_data();
}
//Set initial node value
public function set_data() {
if ($this->node == null) {
echo("\nEmpty Graph");
} else {
for ($index = 0; $index < $this->size; $index++) {
$this->node[$index] = new Vertices($index);
}
}
}
//connect two nodes
public function connect($start, $last, $weight) {
$new_edge = new AjlistNode($last, $weight);
if ($this->node[$start]->next == null) {
$this->node[$start]->next = $new_edge;
} else {
$temp = $this->node[$start]->next;
while ($temp->next != null) {
$temp = $temp->next;
}
$temp->next = $new_edge;
}
}
//Add edge of two nodes
public function add_edge($start, $last, $weight) {
if ($start >= 0 &&
$start < $this->size &&
$last >= 0 &&
$last < $this->size &&
$this->node != null) {
$this->connect($start, $last, $weight);
if ($start != $last) {
$this->connect($last, $start, $weight);
}
} else {
echo("\nHere Something Wrong");
}
}
public function print_graph() {
if ($this->size > 0 &&
$this->node != null) {
for ($index = 0; $index < $this->size; $index++) {
echo("\nAdjacency list of vertex ". $index ." :");
$temp = $this->node[$index]->next;
while ($temp != null) {
echo(" ". $this->node[$temp->id]->data);
$temp = $temp->next;
}
}
}
}
function min_distance( & $distance, & $visit) {
$position = -1;
for ($i = 0; $i < $this->size; ++$i) {
if ($visit[$i] == 0) {
if ($position == -1) {
$position = $i;
} else
if ($distance[$position] > $distance[$i]) {
$position = $i;
}
}
}
return $position;
}
function dijkstra_path($source) {
if ($this->node != null) {
$distance = array_fill(0, $this->size, PHP_INT_MAX);
$visit = array_fill(0, $this->size, 0);
$position = 0;
$i = 0;
$distance[$source] = 0;
$temp = null;
for ($i = 0; $i < $this->size; ++$i) {
$position = $this->min_distance($distance, $visit);
if ($distance[$position] != PHP_INT_MAX) {
$temp = $this->node[$position]->next;
while ($temp != null) {
if ($distance[$position] + $temp->weight < $distance[$temp->id]) {
$distance[$temp->id] = $distance[$position] + $temp->weight;
}
$temp = $temp->next;
}
}
if ($position != -1) {
$visit[$position] = 1;
}
}
echo("\nVertex Distance Source Node (". $source .")\n");
for ($i = 0; $i < $this->size; ++$i) {
if ($distance[$i] == PHP_INT_MAX) {
echo(" ". $i ." \t \t INF\n");
} else {
echo(" ". $i ." \t \t ". $distance[$i] ."\n");
}
}
} else {
echo("Empty Graph");
}
}
}
function main() {
//11 implies the number of nodes in graph
$g = new MyGraph(11);
//Connected two node with Edges
//First two parameter indicates number start and end nodes
//And third parameter indicates weight of edge
$g->add_edge(0, 1, 5);
$g->add_edge(0, 2, 2);
$g->add_edge(0, 3, 4);
$g->add_edge(1, 2, 2);
$g->add_edge(1, 4, 6);
$g->add_edge(2, 3, 1);
$g->add_edge(2, 6, 2);
$g->add_edge(3, 6, 3);
$g->add_edge(4, 5, 7);
$g->add_edge(4, 7, 6);
$g->add_edge(5, 6, 3);
$g->add_edge(5, 7, 8);
$g->add_edge(5, 9, 7);
$g->add_edge(6, 8, 8);
$g->add_edge(6, 9, 4);
$g->add_edge(7, 10, 7);
$g->add_edge(8, 9, 2);
$g->add_edge(8, 10, 7);
$g->add_edge(9, 10, 8);
$g->print_graph();
//source node 0 by default
$g->dijkstra_path(0);
}
main();
Output
Adjacency list of vertex 0 : 1 2 3
Adjacency list of vertex 1 : 0 2 4
Adjacency list of vertex 2 : 0 1 3 6
Adjacency list of vertex 3 : 0 2 6
Adjacency list of vertex 4 : 1 5 7
Adjacency list of vertex 5 : 4 6 7 9
Adjacency list of vertex 6 : 2 3 5 8 9
Adjacency list of vertex 7 : 4 5 10
Adjacency list of vertex 8 : 6 9 10
Adjacency list of vertex 9 : 5 6 8 10
Adjacency list of vertex 10 : 7 8 9
Vertex Distance Source Node (0)
0 0
1 4
2 2
3 3
4 10
5 7
6 4
7 15
8 10
9 8
10 16//Node Js Program
//Dijkstra’s shortest path algorithm
class AjlistNode {
constructor(id, weight) {
//Set value of node key
this.id = id;
this.weight = weight;
this.next = null;
}
}
class Vertices {
constructor(data) {
this.data = data;
this.next = null;
}
}
class MyGraph {
constructor(size) {
//set value
this.size = size;
this.node = Array(size).fill(null);
this.set_data();
}
//Set initial node value
set_data() {
if (this.node == null) {
process.stdout.write("\nEmpty Graph");
} else {
for (var index = 0; index < this.size; index++) {
this.node[index] = new Vertices(index);
}
}
}
//connect two nodes
connect(start, last, weight) {
var new_edge = new AjlistNode(last, weight);
if (this.node[start].next == null) {
this.node[start].next = new_edge;
} else {
var temp = this.node[start].next;
while (temp.next != null) {
temp = temp.next;
}
temp.next = new_edge;
}
}
//Add edge of two nodes
add_edge(start, last, weight) {
if (start >= 0 &&
start < this.size &&
last >= 0 &&
last < this.size &&
this.node != null) {
this.connect(start, last, weight);
if (start != last) {
this.connect(last, start, weight);
}
} else {
process.stdout.write("\nHere Something Wrong");
}
}
print_graph() {
if (this.size > 0 &&
this.node != null) {
for (var index = 0; index < this.size; index++) {
process.stdout.write("\nAdjacency list of vertex " + index + " :");
var temp = this.node[index].next;
while (temp != null) {
process.stdout.write(" " + this.node[temp.id].data);
temp = temp.next;
}
}
}
}
min_distance(distance, visit) {
var position = -1;
for (var i = 0; i < this.size; ++i) {
if (visit[i] == 0) {
if (position == -1) {
position = i;
} else
if (distance[position] > distance[i]) {
position = i;
}
}
}
return position;
}
dijkstra_path(source) {
if (this.node != null) {
var distance = Array(this.size).fill(Number.MAX_VALUE);
var visit = Array(this.size).fill(0);
var position = 0;
var i = 0;
distance[source] = 0;
var temp = null;
for (i = 0; i < this.size; ++i) {
position = this.min_distance(distance, visit);
if (distance[position] != Number.MAX_VALUE) {
temp = this.node[position].next;
while (temp != null) {
if (distance[position] + temp.weight < distance[temp.id]) {
distance[temp.id] = distance[position] + temp.weight;
}
temp = temp.next;
}
}
if (position != -1) {
visit[position] = 1;
}
}
process.stdout.write("\nVertex Distance Source Node (" + source + ")\n");
for (i = 0; i < this.size; ++i) {
if (distance[i] == Number.MAX_VALUE) {
process.stdout.write(" " + i + " \t \t INF\n");
} else {
process.stdout.write(" " + i + " \t \t " + distance[i] + "\n");
}
}
} else {
process.stdout.write("Empty Graph");
}
}
}
function main(args) {
//11 implies the number of nodes in graph
var g = new MyGraph(11);
//Connected two node with Edges
//First two parameter indicates number start and end nodes
//And third parameter indicates weight of edge
g.add_edge(0, 1, 5);
g.add_edge(0, 2, 2);
g.add_edge(0, 3, 4);
g.add_edge(1, 2, 2);
g.add_edge(1, 4, 6);
g.add_edge(2, 3, 1);
g.add_edge(2, 6, 2);
g.add_edge(3, 6, 3);
g.add_edge(4, 5, 7);
g.add_edge(4, 7, 6);
g.add_edge(5, 6, 3);
g.add_edge(5, 7, 8);
g.add_edge(5, 9, 7);
g.add_edge(6, 8, 8);
g.add_edge(6, 9, 4);
g.add_edge(7, 10, 7);
g.add_edge(8, 9, 2);
g.add_edge(8, 10, 7);
g.add_edge(9, 10, 8);
g.print_graph();
//source node 0 by default
g.dijkstra_path(0);
}
main();
Output
Adjacency list of vertex 0 : 1 2 3
Adjacency list of vertex 1 : 0 2 4
Adjacency list of vertex 2 : 0 1 3 6
Adjacency list of vertex 3 : 0 2 6
Adjacency list of vertex 4 : 1 5 7
Adjacency list of vertex 5 : 4 6 7 9
Adjacency list of vertex 6 : 2 3 5 8 9
Adjacency list of vertex 7 : 4 5 10
Adjacency list of vertex 8 : 6 9 10
Adjacency list of vertex 9 : 5 6 8 10
Adjacency list of vertex 10 : 7 8 9
Vertex Distance Source Node (0)
0 0
1 4
2 2
3 3
4 10
5 7
6 4
7 15
8 10
9 8
10 16# Python 3 Program
# Dijkstra’s shortest path algorithm
import sys
class AjlistNode :
# Vertices node key
def __init__(self, id, weight) :
# Set value of node key
self.id = id
self.weight = weight
self.next = None
class Vertices :
def __init__(self, data) :
self.data = data
self.next = None
class MyGraph :
# number of Vertices
def __init__(self, size) :
# set value
self.size = size
self.node = [None] * size
self.set_data()
# Set initial node value
def set_data(self) :
if (self.node == None) :
print("\nEmpty Graph", end = "")
else :
index = 0
while (index < self.size) :
self.node[index] = Vertices(index)
index += 1
# connect two nodes
def connect(self, start, last, weight) :
new_edge = AjlistNode(last, weight)
if (self.node[start].next == None) :
self.node[start].next = new_edge
else :
temp = self.node[start].next
while (temp.next != None) :
temp = temp.next
temp.next = new_edge
# Add edge of two nodes
def add_edge(self, start, last, weight) :
if (start >= 0 and start < self.size
and last >= 0 and last < self.size and self.node != None) :
self.connect(start, last, weight)
if (start != last) :
self.connect(last, start, weight)
else :
print("\nHere Something Wrong", end = "")
def print_graph(self) :
if (self.size > 0 and self.node != None) :
index = 0
while (index < self.size) :
print("\nAdjacency list of vertex ", index ," :", end = "")
temp = self.node[index].next
while (temp != None) :
print(" ", self.node[temp.id].data, end = "")
temp = temp.next
index += 1
def min_distance(self, distance, visit) :
position = -1
i = 0
while (i < self.size) :
if (visit[i] == 0) :
if (position == -1) :
position = i
elif (distance[position] > distance[i]) :
position = i
i += 1
return position
def dijkstra_path(self, source) :
if (self.node != None) :
distance = [sys.maxsize] * self.size
visit = [0] * self.size
position = 0
i = 0
temp = None
i = 0
distance[source]=0
while (i < self.size) :
position = self.min_distance(distance, visit)
if (distance[position] != sys.maxsize) :
temp = self.node[position].next
while (temp != None) :
if (distance[position] + temp.weight < distance[temp.id]) :
distance[temp.id] = distance[position] + temp.weight
temp = temp.next
if (position != -1) :
visit[position] = 1
i += 1
print("\nVertex Distance Source Node (", source ,")\n", end = "")
i = 0
while (i < self.size) :
if (distance[i] == sys.maxsize) :
print(" ", i ," \t \t INF\n", end = "")
else :
print(" ", i ," \t \t ", distance[i] ,"\n", end = "")
i += 1
else :
print("Empty Graph", end = "")
def main() :
g = MyGraph(11)
# Connected two node with Edges
# First two parameter indicates number start and end nodes
# And third parameter indicates weight of edge
g.add_edge(0, 1, 5)
g.add_edge(0, 2, 2)
g.add_edge(0, 3, 4)
g.add_edge(1, 2, 2)
g.add_edge(1, 4, 6)
g.add_edge(2, 3, 1)
g.add_edge(2, 6, 2)
g.add_edge(3, 6, 3)
g.add_edge(4, 5, 7)
g.add_edge(4, 7, 6)
g.add_edge(5, 6, 3)
g.add_edge(5, 7, 8)
g.add_edge(5, 9, 7)
g.add_edge(6, 8, 8)
g.add_edge(6, 9, 4)
g.add_edge(7, 10, 7)
g.add_edge(8, 9, 2)
g.add_edge(8, 10, 7)
g.add_edge(9, 10, 8)
g.print_graph()
g.dijkstra_path(0)
if __name__ == "__main__":
main()
Output
Adjacency list of vertex 0 : 1 2 3
Adjacency list of vertex 1 : 0 2 4
Adjacency list of vertex 2 : 0 1 3 6
Adjacency list of vertex 3 : 0 2 6
Adjacency list of vertex 4 : 1 5 7
Adjacency list of vertex 5 : 4 6 7 9
Adjacency list of vertex 6 : 2 3 5 8 9
Adjacency list of vertex 7 : 4 5 10
Adjacency list of vertex 8 : 6 9 10
Adjacency list of vertex 9 : 5 6 8 10
Adjacency list of vertex 10 : 7 8 9
Vertex Distance Source Node ( 0 )
0 0
1 4
2 2
3 3
4 10
5 7
6 4
7 15
8 10
9 8
10 16# Ruby Program
# Dijkstra’s shortest path algorithm
class AjlistNode
# Define the accessor and reader of class AjlistNode
attr_reader :id, :weight, :next
attr_accessor :id, :weight, :next
def initialize(id, weight)
# Set value of node key
self.id = id
self.weight = weight
self.next = nil
end
end
class Vertices
# Define the accessor and reader of class Vertices
attr_reader :data, :next
attr_accessor :data, :next
def initialize(data)
self.data = data
self.next = nil
end
end
class MyGraph
# Define the accessor and reader of class MyGraph
attr_reader :size, :node
attr_accessor :size, :node
def initialize(size)
# set value
self.size = size
@node = Array.new(size) {nil}
self.set_data()
end # Set initial node value
def set_data()
if (@node == nil)
print("\nEmpty Graph")
else
index = 0
while (index < @size)
@node[index] = Vertices.new(index)
index += 1
end
end
end # connect two nodes
def connect(start, last, weight)
new_edge = AjlistNode.new(last, weight)
if (@node[start].next == nil)
@node[start].next = new_edge
else
temp = @node[start].next
while (temp.next != nil)
temp = temp.next
end
temp.next = new_edge
end
end # Add edge of two nodes
def add_edge(start, last, weight)
if (start >= 0 &&
start < @size &&
last >= 0 &&
last < @size &&
@node != nil)
self.connect(start, last, weight)
if (start != last)
self.connect(last, start, weight)
end
else
print("\nHere Something Wrong")
end
end
def print_graph()
if (@size > 0 &&
@node != nil)
index = 0
while (index < @size)
print("\nAdjacency list of vertex ", index ," :")
temp = @node[index].next
while (temp != nil)
print(" ", @node[temp.id].data)
temp = temp.next
end
index += 1
end
end
end
def min_distance(distance, visit)
position = -1
i = 0
while (i < @size)
if (visit[i] == 0)
if (position == -1)
position = i
elsif (distance[position] > distance[i])
position = i
end
end
i += 1
end
return position
end
def dijkstra_path(source)
if (@node != nil)
distance = Array.new(@size) {(2 ** (0.size * 8 - 2))}
visit = Array.new(@size) {0}
position = 0
i = 0
distance[source] = 0
temp = nil
i = 0
while (i < @size)
position = self.min_distance(distance, visit)
if (distance[position] != (2 ** (0. size * 8 - 2)))
temp = @node[position].next
while (temp != nil)
if (distance[position] + temp.weight < distance[temp.id])
distance[temp.id] = distance[position] + temp.weight
end
temp = temp.next
end
end
if (position != -1)
visit[position] = 1
end
i += 1
end
print("\nVertex Distance Source Node (", source ,")\n")
i = 0
while (i < @size)
if (distance[i] == (2 ** (0. size * 8 - 2)))
print(" ", i ," \t \t INF\n")
else
print(" ", i ," \t \t ", distance[i] ,"\n")
end
i += 1
end
else
print("Empty Graph")
end
end
end
def main()
g = MyGraph.new(11)
# Connected two node with Edges
# First two parameter indicates number start and end nodes
# And third parameter indicates weight of edge
g.add_edge(0, 1, 5)
g.add_edge(0, 2, 2)
g.add_edge(0, 3, 4)
g.add_edge(1, 2, 2)
g.add_edge(1, 4, 6)
g.add_edge(2, 3, 1)
g.add_edge(2, 6, 2)
g.add_edge(3, 6, 3)
g.add_edge(4, 5, 7)
g.add_edge(4, 7, 6)
g.add_edge(5, 6, 3)
g.add_edge(5, 7, 8)
g.add_edge(5, 9, 7)
g.add_edge(6, 8, 8)
g.add_edge(6, 9, 4)
g.add_edge(7, 10, 7)
g.add_edge(8, 9, 2)
g.add_edge(8, 10, 7)
g.add_edge(9, 10, 8)
g.print_graph()
g.dijkstra_path(0)
end
main()
Output
Adjacency list of vertex 0 : 1 2 3
Adjacency list of vertex 1 : 0 2 4
Adjacency list of vertex 2 : 0 1 3 6
Adjacency list of vertex 3 : 0 2 6
Adjacency list of vertex 4 : 1 5 7
Adjacency list of vertex 5 : 4 6 7 9
Adjacency list of vertex 6 : 2 3 5 8 9
Adjacency list of vertex 7 : 4 5 10
Adjacency list of vertex 8 : 6 9 10
Adjacency list of vertex 9 : 5 6 8 10
Adjacency list of vertex 10 : 7 8 9
Vertex Distance Source Node (0)
0 0
1 4
2 2
3 3
4 10
5 7
6 4
7 15
8 10
9 8
10 16
//Scala Program
//Dijkstra’s shortest path algorithm
class AjlistNode(var id: Int,
var next: AjlistNode,
var weight: Int) {
def this(id: Int, weight: Int) {
//Set value
this(id,null,weight);
}
}
class Vertices(var data: Int,
var next: AjlistNode) {
def this(data: Int) {
this(data,null);
}
}
class MyGraph(var size: Int,
var node: Array[Vertices]) {
def this(value: Int) {
//set value
this(value,Array.fill[Vertices](value)(null));
//set initial values of graph node
this.set_data();
}
//Set initial node value
def set_data(): Unit = {
if (this.node == null) {
print("\nEmpty Graph");
} else {
var index: Int = 0;
while (index < this.size) {
this.node(index) = new Vertices(index);
index += 1;
}
}
}
//connect two nodes
def connect(start: Int, last: Int, weight: Int): Unit = {
var new_edge: AjlistNode = new AjlistNode(last, weight);
if (this.node(start).next == null) {
this.node(start).next = new_edge;
} else {
var temp: AjlistNode = this.node(start).next;
while (temp.next != null) {
temp = temp.next;
}
temp.next = new_edge;
}
}
//Add edge of two nodes
def add_edge(start: Int, last: Int, weight: Int): Unit = {
if (start >= 0 &&
start < this.size &&
last >= 0 &&
last < this.size &&
this.node != null) {
connect(start, last, weight);
if (start != last) {
connect(last, start, weight);
}
} else {
print("\nHere Something Wrong");
}
}
def print_graph(): Unit = {
if (this.size > 0 &&
this.node != null) {
var index: Int = 0;
while (index < this.size) {
print("\nAdjacency list of vertex " + index + " :");
var temp: AjlistNode = this.node(index).next;
while (temp != null) {
print(" " + this.node(temp.id).data);
temp = temp.next;
}
index += 1;
}
}
}
def min_distance(distance: Array[Int], visit: Array[Int]): Int = {
var position: Int = -1;
var i: Int = 0;
while (i < this.size) {
if (visit(i) == 0) {
if (position == -1) {
position = i;
} else
if (distance(position) > distance(i)) {
position = i;
}
}
i += 1;
}
return position;
}
def dijkstra_path(source: Int): Unit = {
if (this.node != null) {
var distance: Array[Int] = Array.fill[Int](this.size)(Int.MaxValue);
var visit: Array[Int] = Array.fill[Int](this.size)(0);
var position: Int = 0;
var i: Int = 0;
distance(source) = 0;
var temp: AjlistNode = null;
i = 0;
while (i < this.size) {
position = min_distance(distance, visit);
if (distance(position) != Int.MaxValue) {
temp = this.node(position).next;
while (temp != null) {
if (distance(position) + temp.weight < distance(temp.id)) {
distance(temp.id) = distance(position) + temp.weight;
}
temp = temp.next;
}
}
if (position != -1) {
visit(position) = 1;
}
i += 1;
}
print("\nVertex Distance Source Node (" + source + ")\n");
i = 0;
while (i < this.size) {
if (distance(i) == Int.MaxValue) {
print(" " + i + " \t \t INF\n");
} else {
print(" " + i + " \t \t " + distance(i) + "\n");
}
i += 1;
}
} else {
print("Empty Graph");
}
}
}
object Main {
def main(args: Array[String]): Unit = {
var g: MyGraph = new MyGraph(11);
//Connected two node with Edges
//First two parameter indicates number start and end nodes
//And third parameter indicates weight of edge
g.add_edge(0, 1, 5);
g.add_edge(0, 2, 2);
g.add_edge(0, 3, 4);
g.add_edge(1, 2, 2);
g.add_edge(1, 4, 6);
g.add_edge(2, 3, 1);
g.add_edge(2, 6, 2);
g.add_edge(3, 6, 3);
g.add_edge(4, 5, 7);
g.add_edge(4, 7, 6);
g.add_edge(5, 6, 3);
g.add_edge(5, 7, 8);
g.add_edge(5, 9, 7);
g.add_edge(6, 8, 8);
g.add_edge(6, 9, 4);
g.add_edge(7, 10, 7);
g.add_edge(8, 9, 2);
g.add_edge(8, 10, 7);
g.add_edge(9, 10, 8);
g.print_graph();
g.dijkstra_path(0);
}
}
Output
Adjacency list of vertex 0 : 1 2 3
Adjacency list of vertex 1 : 0 2 4
Adjacency list of vertex 2 : 0 1 3 6
Adjacency list of vertex 3 : 0 2 6
Adjacency list of vertex 4 : 1 5 7
Adjacency list of vertex 5 : 4 6 7 9
Adjacency list of vertex 6 : 2 3 5 8 9
Adjacency list of vertex 7 : 4 5 10
Adjacency list of vertex 8 : 6 9 10
Adjacency list of vertex 9 : 5 6 8 10
Adjacency list of vertex 10 : 7 8 9
Vertex Distance Source Node (0)
0 0
1 4
2 2
3 3
4 10
5 7
6 4
7 15
8 10
9 8
10 16//Swift Program
//Dijkstra’s shortest path algorithm
class AjlistNode {
//Vertices node key
var id: Int;
var weight: Int;
var next: AjlistNode? ;
init(_ id: Int, _ weight: Int) {
//Set value of node key
self.id = id;
self.weight = weight;
self.next = nil;
}
}
class Vertices {
var data: Int;
var next: AjlistNode? ;
init(_ data: Int) {
self.data = data;
self.next = nil;
}
}
class MyGraph {
//number of Vertices
var size: Int;
var node: [Vertices]?=[Vertices]();
init(_ size: Int) {
//set value
self.size = size;
var i = 0;
while (i<size) {
self.node!.append(Vertices(i));
i+=1;
}
}
//Set initial node value
func set_data() {
if (self.node == nil) {
print("\nEmpty Graph", terminator: "");
} else {
var index: Int = 0;
while (index < self.size) {
self.node![index] = Vertices(index);
index += 1;
}
}
}
//connect two nodes
func connect(_ start: Int, _ last: Int, _ weight: Int) {
let new_edge: AjlistNode? = AjlistNode(last, weight);
if (self.node![start].next == nil) {
self.node![start].next = new_edge;
} else {
var temp: AjlistNode? = self.node![start].next;
while (temp!.next != nil) {
temp = temp!.next;
}
temp!.next = new_edge;
}
}
//Add edge of two nodes
func add_edge(_ start: Int, _ last: Int, _ weight: Int) {
if (start >= 0 &&
start < self.size &&
last >= 0 &&
last < self.size &&
self.node != nil) {
self.connect(start, last, weight);
if (start != last) {
self.connect(last, start, weight);
}
} else {
print("\nHere Something Wrong", terminator: "");
}
}
func print_graph() {
if (self.size > 0 &&
self.node != nil) {
var index: Int = 0;
while (index < self.size) {
print("\nAdjacency list of vertex ", index ," :", terminator: "");
var temp: AjlistNode? = self.node![index].next;
while (temp != nil) {
print(" ", self.node![temp!.id].data, terminator: "");
temp = temp!.next;
}
index += 1;
}
}
}
func min_distance(_ distance: [Int], _ visit: [Int]) -> Int {
var position: Int = -1;
var i: Int = 0;
while (i < self.size) {
if (visit[i] == 0) {
if (position == -1) {
position = i;
} else
if (distance[position] > distance[i]) {
position = i;
}
}
i += 1;
}
return position;
}
func dijkstra_path(_ source: Int) {
if (self.node != nil) {
var distance: [Int] = Array(repeating: Int.max, count: self.size);
var visit: [Int] = Array(repeating: 0, count: self.size);
var position: Int = 0;
var i: Int = 0;
distance[source] = 0;
var temp: AjlistNode? = nil;
i = 0;
while (i < self.size) {
position = self.min_distance(distance, visit);
if (distance[position] != Int.max) {
temp = self.node![position].next;
while (temp != nil) {
if (distance[position] + temp!.weight < distance[temp!.id]) {
distance[temp!.id] = distance[position] + temp!.weight;
}
temp = temp!.next;
}
}
if (position != -1) {
visit[position] = 1;
}
i += 1;
}
print("\nVertex Distance Source Node (", source ,")\n", terminator: "");
i = 0;
while (i < self.size) {
if (distance[i] == Int.max) {
print(" ", i ," \t \t INF\n", terminator: "");
} else {
print(" ", i ," \t \t ", distance[i] ,"\n", terminator: "");
}
i += 1;
}
} else {
print("Empty Graph", terminator: "");
}
}
}
func main() {
let g: MyGraph? = MyGraph(11);
//Connected two node with Edges
//First two parameter indicates number start and end nodes
//And third parameter indicates weight of edge
g!.add_edge(0, 1, 5);
g!.add_edge(0, 2, 2);
g!.add_edge(0, 3, 4);
g!.add_edge(1, 2, 2);
g!.add_edge(1, 4, 6);
g!.add_edge(2, 3, 1);
g!.add_edge(2, 6, 2);
g!.add_edge(3, 6, 3);
g!.add_edge(4, 5, 7);
g!.add_edge(4, 7, 6);
g!.add_edge(5, 6, 3);
g!.add_edge(5, 7, 8);
g!.add_edge(5, 9, 7);
g!.add_edge(6, 8, 8);
g!.add_edge(6, 9, 4);
g!.add_edge(7, 10, 7);
g!.add_edge(8, 9, 2);
g!.add_edge(8, 10, 7);
g!.add_edge(9, 10, 8);
g!.print_graph();
g!.dijkstra_path(0);
}
main();
Output
Adjacency list of vertex 0 : 1 2 3
Adjacency list of vertex 1 : 0 2 4
Adjacency list of vertex 2 : 0 1 3 6
Adjacency list of vertex 3 : 0 2 6
Adjacency list of vertex 4 : 1 5 7
Adjacency list of vertex 5 : 4 6 7 9
Adjacency list of vertex 6 : 2 3 5 8 9
Adjacency list of vertex 7 : 4 5 10
Adjacency list of vertex 8 : 6 9 10
Adjacency list of vertex 9 : 5 6 8 10
Adjacency list of vertex 10 : 7 8 9
Vertex Distance Source Node ( 0 )
0 0
1 4
2 2
3 3
4 10
5 7
6 4
7 15
8 10
9 8
10 16
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment