Skip to main content

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:

  1. Initialize the starting node with a distance of 0 and all other nodes with a distance of infinity.
  2. Initialize an empty predecessor dictionary to keep track of the previous nodes in the path.
  3. Create an empty set of visited nodes and add the starting node to it.
  4. While the destination node has not been visited, select the node with the smallest tentative distance from the set of unvisited nodes.
  5. 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.
  6. Add the selected node to the set of visited nodes.
  7. 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
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