Skip to main content

Find Minimum cost from source node to destination

In various applications, finding the minimum cost from a source node to a destination node is a crucial problem. This article tackles this challenge by demonstrating how to calculate the minimum cost of traveling between two nodes in a weighted graph. The code implements a depth-first search (DFS) algorithm to efficiently find the minimum cost path.

Problem Statement and Description

Given a weighted directed graph and two nodes (source and destination), the objective is to find the minimum cost of traveling from the source node to the destination node. The graph is represented using an adjacency list, where each edge has an associated weight. The article aims to explain the problem, provide a step-by-step approach to solve it, and present a working C code implementation.

Example

Find Minimum cost from source node to destination

Idea to Solve the Problem

The problem can be solved using a recursive DFS approach. Starting from the source node, we explore all possible paths to the destination node while keeping track of the total cost. We update the minimum cost whenever a valid path to the destination is found.

Pseudocode

Here's a pseudocode outline to find the minimum cost from the source node to the destination node using DFS:

procedure findMinimumCost(graph, source, destination, visited, result, sum):
    if source or destination is invalid:
        return
    
    if source == destination:
        update result with minimum of current sum and result
    
    mark source as visited
    
    for each adjacent vertex of source:
        recursively call findMinimumCost with updated sum
    
    mark source as unvisited

procedure main():
    create a graph
    
    connect vertices using addEdge function
    
    initialize result with a large value
    
    call findMinimumCost function
    
    print the minimum cost result

main()

Algorithm Explanation

  1. Base case: If the source or destination is invalid, return.
  2. If the source node matches the destination node, update the result with the minimum of the current sum and the stored result.
  3. Mark the source node as visited to avoid revisiting.
  4. Iterate through each adjacent vertex of the source node: a. Recursively call the findMinimumCost function for the adjacent vertex with an updated sum.
  5. Mark the source node as unvisited before exiting the recursive call.

Code Solution

//C Program
//Find Minimum cost from source node to destination
#include <stdio.h>
#include <stdlib.h>
#include <limits.h> //for INT_MAX
struct AjlistNode
{
  int vId;//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 setData(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->vId=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 addEdge(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);
    connect_edge(node,E,V,weight);

  }else
  {
        //not valid Vertices
    printf("Invalid Node Vertices %d  %d", V,E);
  }
}
  //Display Adjacency list of vertex
void printGraph(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->vId is graph node vertices
          //in this case temp->vId is same as 
          //node[temp->vId].data

        printf("  %d",node[temp->vId].data);
        temp=temp->next;
      }
    }
  }else
  {
    printf("Empty Graph");
  }
}



void min_cost(int start,int end,int *visit,struct Graph*node,int*result,int sum)
{

  if(start >size || end >size || start<0 || end<0 || node==NULL)
  {
    //invalid input
    return ;
  }


  if(visit[start]==1)
  {
    return;
  }
  if(start==end)
  {
    if(*result>sum)
    {
      //when get new result
      *result=sum;
    }
  }
  visit[start]=1;
  struct AjlistNode *temp=node[start].next;
  while(temp!=NULL)
  {
    min_cost(temp->vId,end,visit,node,result,sum+temp->weight); 

    temp=temp->next;
  }

  visit[start]=0;
}



int main()

{

  size=6;

  struct Graph*node=NULL;

  int *visit=(int*)calloc(size,sizeof(int));

  node=(struct Graph*)malloc(sizeof(struct Graph)*size);

  if(node==NULL)
  {
    printf("\n Memory overflow");
  }else
  {
    //First set node keys
    setData(node); 

    int result=INT_MAX;


    //Connected two node with Edges

    addEdge(node,0, 2, 9); 
    addEdge(node,0, 3, 7); 
    addEdge(node,0, 5, 1); 

    addEdge(node,1, 0, 3); 
    addEdge(node,1, 5, 8); 

    addEdge(node,2, 3, 7); 
    addEdge(node,2, 5, 15);

    addEdge(node,3, 1, -8); 
    addEdge(node,3, 4, 21); 

    addEdge(node,4, 1, 9); 

    addEdge(node,5, 3, 1); 
    addEdge(node,5, 4, 6); 



    printGraph(node);
    //Source node 0 destination 4
    min_cost(0,4,visit,node,&result,0);

    printf("\n Minimum Cost: %d\n",result );
  }  
  return 0;
}

Output

 Adjacency list of vertex 0  :  2  3  5  1
 Adjacency list of vertex 1  :  0  5  3  4
 Adjacency list of vertex 2  :  0  3  5
 Adjacency list of vertex 3  :  0  2  1  4  5
 Adjacency list of vertex 4  :  3  1  5
 Adjacency list of vertex 5  :  0  1  2  3  4
 Minimum Cost: 2
//C++ program
//Find Minimum cost from source node to destination
#include <iostream>
#include <limits.h> //for INT_MAX
using namespace std;

struct AjlistNode
{
  int vId;//Vertices id
  int weight;
  struct AjlistNode*next;
};

struct Vertices
{
  int data; //node key value
  struct AjlistNode*next;
};


class Graph
{
  Vertices *node;
  int size;//number of 
public:
  Graph(int);
  void setData();
  void addEdge(int,int,int);
  void printGraph();
  void connect(int  ,int ,int);
  void find_min_cost(int ,int);
  void min_cost(int,int ,int* ,int*,int);

};
Graph::Graph(int size)
{
  this->size = size;
    //set number of nodes
  node = new Vertices[size];
}
  //set node key value
void Graph:: setData()
{
  if(node!=NULL)
  {
    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
  {
    cout<<"Vertic Node is Empty"<<endl;
  }
}
  //Add Edge from Two given Nodes
void Graph ::connect(int start ,int end,int weight)
{
    //add edge form start to end
    //start and end is Node location
    //first create Adjacency node
  AjlistNode *newEdge=new AjlistNode;

  if(newEdge!=NULL)
  {

    newEdge->next = NULL;
    newEdge->vId = end;
    newEdge->weight =weight;

    AjlistNode *temp=node[start].next;

    if(temp==NULL)
    {
      node[start].next=newEdge;
    }
    else
    {
        //Add node at last
      while(temp->next!=NULL)
      {
        temp=temp->next;
      }      
      temp->next=newEdge;          
    }
  }

}


void Graph ::  addEdge(int V ,int E, int weight)
{
    //add edge form V to E
    //V and E is Node location
  if(V<size && E <size)
  {
    connect(V,E,weight);

    if(V!=E)
    {
      connect(E,V,weight);
    }
  }else
  {
      //not valid Vertices
    cout<<"Invalid Node Vertices "<< V<<" "<<E;
  }
}

  //Display Adjacency list of vertex
void Graph:: printGraph()
{
  if(node!=NULL)
  {
    AjlistNode *temp=NULL;
    for(int index=0; index < size; index++)
    {
      cout<<"\n Adjacency list of vertex "<<index<<" :";
      temp=node[index].next;
      while(temp!=NULL)
      {
          //temp->vId is graph node vertices
          //in this case temp->vId is same as 
          //node[temp->vId].data

        cout<<" "<<node[temp->vId].data;
        temp=temp->next;
      }
    }
  }
  else
  {
    cout<<"Empty Graph"<<endl;
  }
}



void Graph:: min_cost(int start,
  int end,
  int visit[],
  int*result,
  int sum)
{

  if (start >size || end >size || start<0 || end<0 || node==NULL)
  {
    //invalid input
    return ;
  }
  if (visit[start]==1)
  {
    return;
  }
  if(start==end)
  {
    if(*result>sum)
    {
        //when get new result
      *result=sum;
    }
  }

  visit[start]=1;
  AjlistNode *temp=node[start].next;
  while(temp!=NULL)
  {
    min_cost(temp->vId,end,visit,result,sum+temp->weight); 
    temp=temp->next;
  }
  visit[start]=0;
}
void Graph :: find_min_cost(int source,int destination)
{

  int result = INT_MAX;

  int visit[size];

  for(int i=0;i<size;i++)
  {
    visit[i]=0;
  }
  min_cost(source,destination,visit,&result,0);
  cout<<"\n Minimum Cost in between nodes \
  [ "<< source <<","<< destination <<"] is "<< result<<"\n";
}
int main()
{
  //Create Object
  Graph g=Graph(6); //6 nodes
  //First set node keys
  g.setData();


  g.addEdge(0, 2, 9); 
  g.addEdge(0, 3, 7); 
  g.addEdge(0, 5, 1); 

  g.addEdge(1, 0, 3); 
  g.addEdge(1, 5, 8); 

  g.addEdge(2, 3, 7); 
  g.addEdge(2, 5, 15);

  g.addEdge(3, 1, -8); 
  g.addEdge(3, 4, 21); 

  g.addEdge(4, 1, 9); 

  g.addEdge(5, 3, 1); 
  g.addEdge(5, 4, 6); 
  g.printGraph();

  //value 0 is source node
  int source = 0;
  //value 4 is destination node
  int destination = 4;

  g.find_min_cost(source,destination);

  return 0;
}

Output

 Adjacency list of vertex 0 : 2 3 5 1
 Adjacency list of vertex 1 : 0 5 3 4
 Adjacency list of vertex 2 : 0 3 5
 Adjacency list of vertex 3 : 0 2 1 4 5
 Adjacency list of vertex 4 : 3 1 5
 Adjacency list of vertex 5 : 0 1 2 3 4
 Minimum Cost in between nodes   [ 0,4] is 2
//Java program
//Find Minimum cost from source node to destination
public class MyGraph
{

  static class AjlistNode
  {
    int id;//Vertices node key
    int weight;
    AjlistNode next;
  }
  static class Vertices
  {
    int data;
    AjlistNode next;
  }

  //number of Vertices
  public int size,result;
  Vertices node[];

  MyGraph(int size)
  {
    //set value
    this.size = size;
    result = 1;
    node = new Vertices[size];

  }

  //set initial node value
  public void setData()
  {
    if(node == null)
    {
      System.out.println("\nEmpty Graph");
    }
    else
    {
      for(int index = 0; index < size; index++)
      {
        // avoid java.lang.nullPointerException
        node[index]=new Vertices(); 
        node[index].data=index;//set your data
        node[index].next=null;
      }
    }
  }
    //connect two nodes
  public void connect(int start,int end ,int weight)
  {
    AjlistNode newEdge=new AjlistNode();
    newEdge.id=end;//end node
    newEdge.next=null;
    newEdge.weight=weight;
    if(node[start].next==null)
    {
      node[start].next=newEdge;
    }else
    {
      AjlistNode temp=node[start].next;

      while(temp.next!=null)
      {
        temp=temp.next;
      }
      temp.next=newEdge;
    }
  }
    //Add edge of two nodes
  public void addEdge(int start,int end,int weight)
  {
    if(start < size && end < size && node != null)
    {
      connect(start,end,weight);
      if(start!=end)
      {
        connect(end,start,weight);  
      }

    }else
    {
      System.out.println("\nEmpty Graph");
    }
  }

  public void printGraph()
  {

    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;
        }
      }
    }
  }
  public void min_cost(int start,
    int end,
    boolean []visit,
    int sum)
  {

    if (start >size || end >size || start<0 || end<0 || node==null)
    {
      //invalid input
      return ;
    }
    if (visit[start]==true)
    {
      return;
    }
    if (start==end)
    {
      if ( sum <  result)
      {
        result=sum;
      }
    }
    visit[start]=true;
    AjlistNode temp=node[start].next;
    while(temp!=null)
    {
      min_cost(temp.id,end,visit,sum+temp.weight); 
      temp=temp.next;
    }
    visit[start]=false;
  }
  public void  find_min_cost(int source,int destination)
  {
    //For resultant 
    result=Integer.MAX_VALUE;
    boolean []visit=new boolean[size];
    for(int i=0; i < size; i++)
    {
      visit[i]=false;
    }
    min_cost(source,destination,visit,0);
    System.out.println("\n Minimum Cost in between nodes ["+ source +","+ destination +"] is "+ result+"\n");
  }

  public static void main(String[] args) 
  {
    int totalNode=6;

    MyGraph g=new MyGraph(totalNode);

    g.setData();

    g.addEdge(0, 2, 9); 
    g.addEdge(0, 3, 7); 
    g.addEdge(0, 5, 1); 

    g.addEdge(1, 0, 3); 
    g.addEdge(1, 5, 8); 

    g.addEdge(2, 3, 7); 
    g.addEdge(2, 5, 15);

    g.addEdge(3, 1, -8); 
    g.addEdge(3, 4, 21); 

    g.addEdge(4, 1, 9); 

    g.addEdge(5, 3, 1); 
    g.addEdge(5, 4, 6); 
    g.printGraph();

        //value 0 is source node
    int source = 0;
        //value 4 is destination node
    int destination = 4;

    g.find_min_cost(source,destination);

  }
}

Output

Adjacency list of vertex 0 :  2  3  5  1
Adjacency list of vertex 1 :  0  5  3  4
Adjacency list of vertex 2 :  0  3  5
Adjacency list of vertex 3 :  0  2  1  4  5
Adjacency list of vertex 4 :  3  1  5
Adjacency list of vertex 5 :  0  1  2  3  4
 Minimum Cost in between nodes [0,4] is 2
#Python Program 
#Find Minimum cost from source node to destination
import sys
#Python program
#Minimum number of edges between two vertices of a Graph
class AjLinkeNode:
  def __init__(self,data,weight):
    self.id = data
    self.weight = weight
    self.next = None

class Vertices:
  def __init__(self,data):
    self.data=data
    self.next=None

class Graph:
  """Constructor for Graph"""
  def __init__(self, size):
    self.size=size
    self.node=[]
    self.result=0
    

  def setData(self):
    if(self.size>0 and self.node!=None):

      index=0
      while(index<self.size):

        self.node.append(Vertices(index))

        index+=1


  #connect two node with  edge
  def connect(self,start,end,weight):

    new_edge=AjLinkeNode(end,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
  def addEdge(self,start,end,weight):
     
    #start,end is two nodes
    if(self.size > start and self.size > start):
      
      self.connect(start,end,weight)
      if(start!=end):
      
        self.connect(end,start,weight)
      

    else:
      print("Invalid nodes")


  def printGraph(self):

    if(self.size>0 and self.node!=None):

      index=0

      while(index < self.size):

        print("\nAdjacency list of vertex {0} : ".format(index),end=" ")
        
        temp=self.node[index].next
        
        while temp!=None:

          print(" {0}".format(temp.id),end=" ")

          temp=temp.next

        index+=1

  

  def min_cost(self,start,end,visit,node_sum) :

    if (start >self.size  or  end >self.size or start<0 or end<0 or self.node==None) :

      #invalid input
      return 
    if (visit[start]==True) :

      return
    if (start==end) :

      if (node_sum < self.result) :

        self.result=node_sum

    visit[start]=True

    temp=self.node[start].next

    while(temp!=None) :

      self.min_cost(temp.id,end,visit,node_sum +temp.weight) 
      temp=temp.next
    visit[start]=False

  def  find_min_cost(self,source,destination) :

    #for resultant paths
    self.result=sys.maxsize
    visit=[False]*self.size

    self.min_cost(source,destination,visit,0)
    print("\n  Minimum Cost in between nodes [",source,",",destination,"] : ",self.result)
    


    
def main():
  g=Graph(6)
  g.setData() 

  #Connected two node with Edges
  g.addEdge(0, 2, 9); 
  g.addEdge(0, 3, 7); 
  g.addEdge(0, 5, 1); 

  g.addEdge(1, 0, 3); 
  g.addEdge(1, 5, 8); 

  g.addEdge(2, 3, 7); 
  g.addEdge(2, 5, 15);

  g.addEdge(3, 1, -8); 
  g.addEdge(3, 4, 21); 

  g.addEdge(4, 1, 9); 

  g.addEdge(5, 3, 1); 
  g.addEdge(5, 4, 6); 
  g.printGraph()
  #value 0 is source node
  source = 0
  #value 4 is destination node
  destination = 4
  g.find_min_cost(source,destination)

if __name__=="__main__":
    main()

Output

Adjacency list of vertex 0 :   2  3  5  1 
Adjacency list of vertex 1 :   0  5  3  4 
Adjacency list of vertex 2 :   0  3  5 
Adjacency list of vertex 3 :   0  2  1  4  5 
Adjacency list of vertex 4 :   3  1  5 
Adjacency list of vertex 5 :   0  1  2  3  4 
  Minimum Cost in between nodes [ 0 , 4 ] :  2
//C# program
//Find Minimum cost from source node to destination
using System;
public class AjlistNode
{
  public int id;//Vertices node key
  public int weight;
  public AjlistNode next;
}
public class Vertices
{
  public int data;
  public AjlistNode next;
}
public class MyGraph
{

  //number of Vertices
  public int size,result;
  public Vertices []node;

  MyGraph(int size)
  {
    //set value
    this.size = size;
    result = 1;
    node = new Vertices[size];

  }

  //set initial node value
  public void setData()
  {
    if(node == null)
    {
      Console.WriteLine("\nEmpty Graph");
    }
    else
    {
      for(int index = 0; index < size; index++)
      {
        // avoid java.lang.nullPointerException
        node[index]=new Vertices(); 
        node[index].data=index;//set your data
        node[index].next=null;
      }
    }
  }
  //connect two nodes
  public void connect(int start,int end ,int weight)
  {
    AjlistNode newEdge=new AjlistNode();
    newEdge.id=end;//end node
    newEdge.next=null;
    newEdge.weight=weight;
    if(node[start].next==null)
    {
      node[start].next=newEdge;
    }else
    {
      AjlistNode temp=node[start].next;

      while(temp.next!=null)
      {
        temp=temp.next;
      }
      temp.next=newEdge;
    }
  }
  //Add edge of two nodes
  public void addEdge(int start,int end,int weight)
  {
    if(start < size && end < size && node != null)
    {
      connect(start,end,weight);
      if(start!=end)
      {
        connect(end,start,weight);  
      }

    }else
    {
      Console.WriteLine("\nEmpty Graph");
    }
  }

  public void printGraph()
  {

    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 void min_cost(int start,
    int end,
    Boolean []visit,
    int sum)
  {

    if (start >size || end >size || start<0 || end<0 || node==null)
    {
      //invalid input
      return ;
    }
    if (visit[start]==true)
    {
      return;
    }
    if (start==end)
    {
      if ( sum <  result)
      {
        result=sum;
      }
    }
    visit[start]=true;
    AjlistNode temp=node[start].next;
    while(temp!=null)
    {
      min_cost(temp.id,end,visit,sum+temp.weight); 
      temp=temp.next;
    }
    visit[start]=false;
  }
  public void  find_min_cost(int source,int destination)
  {
    //For resultant 
    result=int.MaxValue;
    Boolean []visit=new Boolean[size];
    for(int i=0; i < size; i++)
    {
      visit[i]=false;
    }
    min_cost(source,destination,visit,0);
    Console.WriteLine("\n Minimum Cost in between nodes ["+ source +","+ destination +"] is "+ result+"\n");
  }

  public static void Main(String[] args) 
  {
    int totalNode=6;

    MyGraph g=new MyGraph(totalNode);

    g.setData();

    g.addEdge(0, 2, 9); 
    g.addEdge(0, 3, 7); 
    g.addEdge(0, 5, 1); 

    g.addEdge(1, 0, 3); 
    g.addEdge(1, 5, 8); 

    g.addEdge(2, 3, 7); 
    g.addEdge(2, 5, 15);

    g.addEdge(3, 1, -8); 
    g.addEdge(3, 4, 21); 

    g.addEdge(4, 1, 9); 

    g.addEdge(5, 3, 1); 
    g.addEdge(5, 4, 6); 
    g.printGraph();

    //value 0 is source node
    int source = 0;
    //value 4 is destination node
    int destination = 4;

    g.find_min_cost(source,destination);

  }
}

Output

Adjacency list of vertex 0 :  2  3  5  1
Adjacency list of vertex 1 :  0  5  3  4
Adjacency list of vertex 2 :  0  3  5
Adjacency list of vertex 3 :  0  2  1  4  5
Adjacency list of vertex 4 :  3  1  5
Adjacency list of vertex 5 :  0  1  2  3  4
 Minimum Cost in between nodes [0,4] is 2
<?php 
/*
* PHP Program 
  Find Minimum cost from source node to destination
*/

  class AjlistNode
  {
    public $vId;
    public $weight;
    public $next;
    function __construct($vId,$weight)
    {
      $this->weight=$weight;
      $this->vId=$vId;
      $this->next=NULL;
    }
  }
  class Node
  {
    public $data;
    public $next;
    function __construct($data)
    {
      $this->data=$data;
      $this->next=NULL;

    }
  }
  class MyGraph
  {

    public $node;
    public $size;
    function __construct($size)
    {
      $this->size=$size;
    $this->node=[];  //empty array
  }
  public function setData()
  {
    if($this->size>0)
    {
      for($index=0;$index<$this->size;$index++)
      {
        $this->node[$index]=new Node($index);
      }

    }
  }
  public function connect($start,$end,$weight)
  {
    $newEdge=new AjlistNode($end,$weight);
    if($this->node[$start]->next==NULL)
    {
      $this->node[$start]->next=$newEdge;
    }
    else
    {

      $temp=$this->node[$start]->next;
      while($temp->next!=NULL)
      {
        $temp=$temp->next;
      }
      $temp->next= $newEdge;
    }
  }
  public function addEdge($start,$end,$weight)
  {
    if($this->size > $start && $this->size>$end)
    {
      $this->connect($start,$end,$weight);
      if($start!=$end)
      {
        $this->connect($end,$start,$weight);
      }
    }
    else
    {
      echo "\n Invalid node";
    }
  }
  public function printGraph()
  {
    if($this->size>0 && count($this->node)>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->vId]->data);
          $temp=$temp->next;
        }
      }
    }
  }
  public function  min_cost($start,$end,$visit,&$result,$sum)
  {

    if ($start > $this->size|| $end>$this->size|| $start<0|| $end<0|| $this->node==NULL)
    {
      //invalid input
      return ;
    }
    if ($visit[$start]==true)
    {
      return;
    }
    if ($start== $end)
    {
      if ($sum<$result)
      {
        $result= $sum;
      }
    }
    $visit[$start]=true;
    $temp =  $this->node[$start]->next;
    while($temp!=NULL)
    {
      $this->min_cost($temp->vId,$end,$visit,$result,$sum+$temp->weight); 
      $temp=$temp->next;
    }
    $visit[$start]=false;
  }

  public function find_min_cost($source,$destination)
  {
    //for resultant paths
    $result= PHP_INT_MAX;
    $visit= array_fill(0, $this->size, false);
    $this->min_cost($source,$destination,$visit,$result,0);
    echo "\n Minimum Cost in between nodes[". $source.",". $destination."] is ". $result."\n";
  }

}


function main()
{
  //create object
  $g=new MyGraph(6);
  $g->setData();

  //Connected two node with Edges
  $g->addEdge(0, 2, 9); 
  $g->addEdge(0, 3, 7); 
  $g->addEdge(0, 5, 1); 

  $g->addEdge(1, 0, 3); 
  $g->addEdge(1, 5, 8); 

  $g->addEdge(2, 3, 7); 
  $g->addEdge(2, 5, 15);

  $g->addEdge(3, 1, -8); 
  $g->addEdge(3, 4, 21); 

  $g->addEdge(4, 1, 9); 

  $g->addEdge(5, 3, 1); 
  $g->addEdge(5, 4, 6); 
  
  $g->printGraph();
  
  //value 0 is source node
  $source=0;
  //value 4 is destination node
  $destination=4;
  
  $g->find_min_cost($source,$destination);

}
main();
?>

Output

Adjacency list of vertex 0 :   2  3  5  1
Adjacency list of vertex 1 :   0  5  3  4
Adjacency list of vertex 2 :   0  3  5
Adjacency list of vertex 3 :   0  2  1  4  5
Adjacency list of vertex 4 :   3  1  5
Adjacency list of vertex 5 :   0  1  2  3  4
 Minimum Cost in between nodes[0,4] is 2

Time Complexity

In the worst case, the DFS algorithm explores all possible paths from the source to the destination. The time complexity is therefore proportional to the number of paths in the graph, which can be exponential. However, the actual number of paths explored depends on the graph structure and the connectivity between nodes.





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