Print all path in Dijkstra’s algorithm
Dijkstra's algorithm is a graph search algorithm used to find the shortest path between two nodes in a graph. It starts by assigning a tentative distance to all nodes, with the starting node having a distance of 0 and all other nodes having a distance of infinity. It then iteratively selects the node with the smallest tentative distance and updates the distances of its neighboring nodes. This process continues until the destination node is reached or all reachable nodes have been visited.
To print all paths using Dijkstra's algorithm, we can use a modified version of the algorithm that keeps track of the paths taken to each node. We can use a dictionary to store the predecessor node for each node in the path. Once we have found the shortest path to the destination node, we can backtrack from the destination node to the starting node using the predecessor dictionary and print out all the paths.
Here are the steps to print all paths using Dijkstra's algorithm:
- Initialize the starting node with a distance of 0 and all other nodes with a distance of infinity.
- Initialize an empty predecessor dictionary to keep track of the previous nodes in the path.
- Create an empty set of visited nodes and add the starting node to it.
- While the destination node has not been visited, select the node with the smallest tentative distance from the set of unvisited nodes.
- For each neighboring node of the selected node, calculate the tentative distance from the starting node and update the distance and predecessor dictionary if it is smaller than the current tentative distance.
- Add the selected node to the set of visited nodes.
- Backtrack from the destination node to the starting node using the predecessor dictionary and print out all the paths.
By using these steps, we can find the shortest path between two nodes and print out all possible paths in a graph using Dijkstra's algorithm.
Code Solution
//C Program
//Print all path in Dijkstra’s 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 *newEdge=(struct AjlistNode*)malloc(
sizeof(struct AjlistNode)
);
if(newEdge!=NULL)
{
newEdge->next=NULL;
newEdge->id=E;
newEdge->weight=weight;
struct AjlistNode *temp=node[V].next;
if(temp==NULL)
{
node[V].next=newEdge;
}else
{
//Add node at last
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=newEdge;
}
}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 path
if(V<size && E <size)
{
connect_edge(node,V,E,weight);
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 view_path(int path[], int location)
{
if (path[location] == - 1) {
return;
}
view_path(path, path[location]);
printf("%d ", location);
}
void bellman_ford(struct Graph*root,int source)
{
if(root!=NULL)
{
int distance[size],visit[size],path[size],position=0;
for (int i = 0; i < size; ++i)
{
//Initial distance is infinity
distance[i] = INF;
//Initial no node visit
visit[i] = 0;
//initial path is -1
path[i] = -1;
}
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] )
{
path[temp->id] = position;
distance[temp->id] = distance[position] + temp->weight;
}
temp=temp->next;
}
}
if(position!=-1)
{
visit[position]=1;
}
}
printf("\nSource Node : %d",source);
printf("\nVertex \tDistance Path\n");
for (int i = 0; i < size; ++i)
{
if(distance[i]==INF)
{
printf(" %d \t INF\n", i);
}
else
{
printf("\n %d \t %d\t %d ", i, distance[i],source);
}
view_path(path,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);
bellman_ford(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
Source Node : 0
Vertex Distance Path
0 0 0
1 4 0 2 1
2 2 0 2
3 3 0 2 3
4 10 0 2 1 4
5 7 0 2 6 5
6 4 0 2 6
7 15 0 2 6 5 7
8 10 0 2 6 9 8
9 8 0 2 6 9
10 16 0 2 6 9 10
//C++ Program
//Print all path in Dijkstra’s algorithm
#include<iostream>
#include <limits.h>
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 view_path(int path[], int location) {
if (path[location] == -1) {
return;
}
this->view_path(path, path[location]);
cout << " " << location;
}
void dijkstra_path(int source) {
if (node != NULL) {
int *distance = new int[size];
int *visit = new int[size];
int *path = new int[size];
int position = 0;
int i = 0;
for (i = 0; i < this->size; ++i) {
distance[i] = INT_MAX;
visit[i] = 0;
path[i] = -1;
}
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;
path[temp->id] = position;
}
temp = temp->next;
}
}
if (position != -1) {
visit[position] = 1;
}
}
cout << "\nVertex Distance Path\n";
for (i = 0; i < this->size; ++i) {
if (distance[i] == INT_MAX) {
cout << " " << i << " \t INF\n";
} else {
cout << " " << i << " \t " << distance[i] << "\t" << source;
}
this->view_path(path, i);
cout << "\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 Path
0 0 0
1 4 0 2 1
2 2 0 2
3 3 0 2 3
4 10 0 2 1 4
5 7 0 2 6 5
6 4 0 2 6
7 15 0 2 6 5 7
8 10 0 2 6 9 8
9 8 0 2 6 9
10 16 0 2 6 9 10
//C# Program
//Print all path in Dijkstra’s 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;
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;
}
}
}
}
public 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;
}
public void view_path(int[] path, int location) {
if (path[location] == -1) {
return;
}
view_path(path, path[location]);
Console.Write(" " + location);
}
public void dijkstra_path(int source) {
if (node != null) {
int[] distance = new int[size];
int[] visit = new int[size];
int[] path = new int[size];
int position = 0;
int i = 0;
for (i = 0; i < size; ++i) {
distance[i] = int.MaxValue;
visit[i] = 0;
path[i] = -1;
}
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;
path[temp.id] = position;
}
temp = temp.next;
}
}
if (position != -1) {
visit[position] = 1;
}
}
Console.Write("\nVertex Distance Path\n");
for (i = 0; i < size; ++i) {
if (distance[i] == int.MaxValue) {
Console.Write(" " + i + " \t INF\n");
} else {
Console.Write(" " + i + " \t " + distance[i] + "\t" + source);
}
view_path(path, i);
Console.Write("\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 Path
0 0 0
1 4 0 2 1
2 2 0 2
3 3 0 2 3
4 10 0 2 1 4
5 7 0 2 6 5
6 4 0 2 6
7 15 0 2 6 5 7
8 10 0 2 6 9 8
9 8 0 2 6 9
10 16 0 2 6 9 10
<?php
//Php Program
//Print all path in Dijkstra’s 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;
}
}
}
}
public 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;
}
public function view_path( & $path, $location) {
if ($path[$location] == -1) {
return;
}
$this->view_path($path, $path[$location]);
echo(" ". $location);
}
public function dijkstra_path($source) {
if ($this->node != null) {
$distance = array_fill(0, $this->size, PHP_INT_MAX);
$visit = array_fill(0, $this->size, 0);
$path = array_fill(0, $this->size, -1);
$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;
$path[$temp->id] = $position;
}
$temp = $temp->next;
}
}
if ($position != -1) {
$visit[$position] = 1;
}
}
echo("\nVertex Distance Path\n");
for ($i = 0; $i < $this->size; ++$i) {
if ($distance[$i] == PHP_INT_MAX) {
echo(" ". $i ." \t INF\n");
} else {
echo(" ". $i ." \t ". $distance[$i] ."\t". $source);
}
$this->view_path($path, $i);
echo("\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 Path
0 0 0
1 4 0 2 1
2 2 0 2
3 3 0 2 3
4 10 0 2 1 4
5 7 0 2 6 5
6 4 0 2 6
7 15 0 2 6 5 7
8 10 0 2 6 9 8
9 8 0 2 6 9
10 16 0 2 6 9 10
//Node Js Program
//Print all path in Dijkstra’s algorithm
class AjlistNode {
//Vertices node key
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 {
//number of Vertices
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;
}
view_path(path, location) {
if (path[location] == -1) {
return;
}
this.view_path(path, path[location]);
process.stdout.write(" " + location);
}
dijkstra_path(source) {
if (this.node != null) {
var distance = Array(this.size).fill(Number.MAX_VALUE);
var visit = Array(this.size).fill(0);
var path = Array(this.size).fill(-1);
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;
path[temp.id] = position;
}
temp = temp.next;
}
}
if (position != -1) {
visit[position] = 1;
}
}
process.stdout.write("\nVertex Distance Path\n");
for (i = 0; i < this.size; ++i) {
if (distance[i] == Number.MAX_VALUE) {
process.stdout.write(" " + i + " \t INF\n");
} else {
process.stdout.write(" " + i + " \t " + distance[i] + "\t" + source);
}
this.view_path(path, i);
process.stdout.write("\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 Path
0 0 0
1 4 0 2 1
2 2 0 2
3 3 0 2 3
4 10 0 2 1 4
5 7 0 2 6 5
6 4 0 2 6
7 15 0 2 6 5 7
8 10 0 2 6 9 8
9 8 0 2 6 9
10 16 0 2 6 9 10
# Python 3 Program
# Print all path in Dijkstra’s 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 view_path(self, path, location) :
if (path[location] == -1) :
return
self.view_path(path, path[location])
print(" ", location, end = "")
def dijkstra_path(self, source) :
if (self.node != None) :
distance = [sys.maxsize] * self.size
visit = [0] * self.size
path = [-1] * self.size
position = 0
distance[source] = 0
temp = None
i = 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
path[temp.id] = position
temp = temp.next
if (position != -1) :
visit[position] = 1
i += 1
print("\nVertex Distance Path\n", end = "")
i = 0
while (i < self.size) :
if (distance[i] == sys.maxsize) :
print(" ", i ," \t INF\n", end = "")
else :
print(" ", i ," \t ", distance[i] ,"\t", source, end = "")
self.view_path(path, i)
print("\n", end = "")
i += 1
else :
print("Empty Graph", end = "")
def main() :
# 11 implies the number of nodes in graph
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)
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 Path
0 0 0
1 4 0 2 1
2 2 0 2
3 3 0 2 3
4 10 0 2 1 4
5 7 0 2 6 5
6 4 0 2 6
7 15 0 2 6 5 7
8 10 0 2 6 9 8
9 8 0 2 6 9
10 16 0 2 6 9 10
# Ruby Program
# Print all path in Dijkstra’s algorithm
class AjlistNode
# Define the accessor and reader of class AjlistNode
attr_reader :id, :weight, :next
attr_accessor :id, :weight, :next
# Vertices node key
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
# number of Vertices
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 view_path(path, location)
if (path[location] == -1)
return
end
self.view_path(path, path[location])
print(" ", location)
end
def dijkstra_path(source)
if (@node != nil)
distance = Array.new(@size) {(2 ** (0. size * 8 - 2))}
visit = Array.new(@size) {0}
path = Array.new(@size) {-1}
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
path[temp.id] = position
end
temp = temp.next
end
end
if (position != -1)
visit[position] = 1
end
i += 1
end
print("\nVertex Distance Path\n")
i = 0
while (i < @size)
if (distance[i] == (2 ** (0. size * 8 - 2)))
print(" ", i ," \t INF\n")
else
print(" ", i ," \t ", distance[i] ,"\t", source)
end
self.view_path(path, i)
print("\n")
i += 1
end
else
print("Empty Graph")
end
end
end
def main()
# 11 implies the number of nodes in graph
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()
# Source node 0 by default
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 Path
0 0 0
1 4 0 2 1
2 2 0 2
3 3 0 2 3
4 10 0 2 1 4
5 7 0 2 6 5
6 4 0 2 6
7 15 0 2 6 5 7
8 10 0 2 6 9 8
9 8 0 2 6 9
10 16 0 2 6 9 10
//Scala Program
//Print all path in Dijkstra’s 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 (node == null) {
print("\nEmpty Graph");
} else {
var index: Int = 0;
while (index < size) {
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 (node(start).next == null) {
node(start).next = new_edge;
} else {
var temp: AjlistNode = 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 < size &&
last >= 0 &&
last < size &&
node != null) {
connect(start, last, weight);
if (start != last) {
connect(last, start, weight);
}
} else {
print("\nHere Something Wrong");
}
}
def print_graph(): Unit = {
if (size > 0 &&
node != null) {
var index: Int = 0;
while (index < size) {
print("\nAdjacency list of vertex " + index + " :");
var temp: AjlistNode = node(index).next;
while (temp != null) {
print(" " + 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 < size) {
if (visit(i) == 0) {
if (position == -1) {
position = i;
} else
if (distance(position) > distance(i)) {
position = i;
}
}
i += 1;
}
return position;
}
def view_path(path: Array[Int], location: Int): Unit = {
if (path(location) == -1) {
return;
}
view_path(path, path(location));
print(" " + location);
}
def dijkstra_path(source: Int): Unit = {
if (node != null) {
var distance: Array[Int]= Array.fill[Int](this.size)(Int.MaxValue);
var visit: Array[Int]= Array.fill[Int](this.size)(0);
var path: Array[Int]= Array.fill[Int](this.size)(-1);
var position: Int = 0;
var i: Int = 0;
distance(source) = 0;
var temp: AjlistNode = null;
while (i < size) {
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;
path(temp.id) = position;
}
temp = temp.next;
}
}
if (position != -1) {
visit(position) = 1;
}
i += 1;
}
print("\nVertex Distance Path\n");
i = 0;
while (i < size) {
if (distance(i) == Int.MaxValue) {
print(" " + i + " \t INF\n");
} else {
print(" " + i + " \t " + distance(i) + "\t" + source);
}
view_path(path, i);
print("\n");
i += 1;
}
} else {
print("Empty Graph");
}
}
}
object Main {
def main(args: Array[String]): Unit = {
//11 implies the number of nodes in graph
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();
//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 Path
0 0 0
1 4 0 2 1
2 2 0 2
3 3 0 2 3
4 10 0 2 1 4
5 7 0 2 6 5
6 4 0 2 6
7 15 0 2 6 5 7
8 10 0 2 6 9 8
9 8 0 2 6 9
10 16 0 2 6 9 10
//Swift Program
//Print all path in Dijkstra’s 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;
}
}
//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 view_path(_ path: [Int], _ location: Int) {
if (path[location] == -1) {
return;
}
self.view_path(path, path[location]);
print(" ", location, terminator: "");
}
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 path: [Int] = Array(repeating: -1, count: self.size);
var position: Int = 0;
var i: Int = 0;
distance[source] = 0;
var temp: AjlistNode? = nil;
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;
path[temp!.id] = position;
}
temp = temp!.next;
}
}
if (position != -1) {
visit[position] = 1;
}
i += 1;
}
print("\nVertex Distance Path\n", terminator: "");
i = 0;
while (i < self.size) {
if (distance[i] == Int.max) {
print(" ", i ," \t INF\n", terminator: "");
} else {
print(" ", i ," \t ", distance[i] ,"\t", source, terminator: "");
}
self.view_path(path, i);
print("\n", terminator: "");
i += 1;
}
} else {
print("Empty Graph", terminator: "");
}
}
}
func main() {
//11 implies the number of nodes in graph
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();
//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 Path
0 0 0
1 4 0 2 1
2 2 0 2
3 3 0 2 3
4 10 0 2 1 4
5 7 0 2 6 5
6 4 0 2 6
7 15 0 2 6 5 7
8 10 0 2 6 9 8
9 8 0 2 6 9
10 16 0 2 6 9 10
//C++ Program
//Print all path in Dijkstra’s algorithm
#include<iostream>
#include <limits.h>
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 view_path(int path[], int location) {
if (path[location] == -1) {
return;
}
this->view_path(path, path[location]);
cout << " " << location;
}
void dijkstra_path(int source) {
if (node != NULL) {
int *distance = new int[size];
int *visit = new int[size];
int *path = new int[size];
int position = 0;
int i = 0;
for (i = 0; i < this->size; ++i) {
distance[i] = INT_MAX;
visit[i] = 0;
path[i] = -1;
}
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;
path[temp->id] = position;
}
temp = temp->next;
}
}
if (position != -1) {
visit[position] = 1;
}
}
cout << "\nVertex Distance Path\n";
for (i = 0; i < this->size; ++i) {
if (distance[i] == INT_MAX) {
cout << " " << i << " INF\n";
} else {
cout << " " << i << " " << distance[i] << " " << source;
}
this->view_path(path, i);
cout << "\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 Path
0 0 0
1 4 0 2 1
2 2 0 2
3 3 0 2 3
4 10 0 2 1 4
5 7 0 2 6 5
6 4 0 2 6
7 15 0 2 6 5 7
8 10 0 2 6 9 8
9 8 0 2 6 9
10 16 0 2 6 9 10
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