Skip to main content

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
Last updated on by Kalkicode




Comment

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