Find Maximum cost from source node to destination

Here given code implementation process.
//C Program
//Find Maximum 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 max_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)
{
max_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_MIN;
//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
max_cost(0,4,visit,node,&result,0);
printf("\n Maximum 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: 54
//C++ program
//Find maximum cost from source node to destination
#include <iostream>
#include <limits.h> //for INT_MIN
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_max_cost(int ,int);
void max_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:: max_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)
{
max_cost(temp->vId,end,visit,result,sum+temp->weight);
temp=temp->next;
}
visit[start]=0;
}
void Graph :: find_max_cost(int source,int destination)
{
int result = INT_MIN;
int visit[size];
for(int i=0;i<size;i++)
{
visit[i]=0;
}
max_cost(source,destination,visit,&result,0);
cout<<"\n Maximum 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_max_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
Maximum Cost in between nodes [ 0,4] is 54
//Java program
//Find Maximum 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 max_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)
{
max_cost(temp.id,end,visit,sum+temp.weight);
temp=temp.next;
}
visit[start]=false;
}
public void find_max_cost(int source,int destination)
{
//For resultant
result=Integer.MIN_VALUE;
boolean []visit=new boolean[size];
for(int i=0; i < size; i++)
{
visit[i]=false;
}
max_cost(source,destination,visit,0);
System.out.println("\n Maximum 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_max_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
Maximum Cost in between nodes [0,4] is 54
#Python Program
#Find maximum cost from source node to destination
import sys
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 max_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.max_cost(temp.id,end,visit,node_sum +temp.weight)
temp=temp.next
visit[start]=False
def find_max_cost(self,source,destination) :
#for resultant paths
self.result=-sys.maxsize-1
visit=[False]*self.size
self.max_cost(source,destination,visit,0)
print("\n Maximum 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_max_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
Maximum Cost in between nodes [ 0 , 4 ] : 54
//C# program
//Find maximum 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.MinValue;
Boolean []visit=new Boolean[size];
for(int i=0; i < size; i++)
{
visit[i]=false;
}
min_cost(source,destination,visit,0);
Console.WriteLine("\n Maximum 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
Maximum Cost in between nodes [0,4] is 54
<?php
/*
* PHP Program
Find maximum 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 max_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->max_cost($temp->vId,$end,$visit,$result,$sum+$temp->weight);
$temp=$temp->next;
}
$visit[$start]=false;
}
public function find_max_cost($source,$destination)
{
//for resultant paths
$result= PHP_INT_MIN;
$visit= array_fill(0, $this->size, false);
$this->max_cost($source,$destination,$visit,$result,0);
echo "\n Maximum 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_max_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
Maximum Cost in between nodes[0,4] is 54
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