Scribd
Upload
5 views2 pages

Java Code To Run A Complex Store Calculation

The document presents a Java implementation of a greedy algorithm for finding the shortest path in a connected graph, specifically designed for a graph with 5 nodes. It defines a Node class to represent each city and its connections, and includes methods for initializing nodes and calculating the shortest paths from a starting node. The algorithm processes nodes based on their adjacency information and path costs, ultimately aiming to reach a designated goal node while handling cases of limited search.

Uploaded by

Vincent Azuka
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
5 views2 pages

Java Code To Run A Complex Store Calculation

The document presents a Java implementation of a greedy algorithm for finding the shortest path in a connected graph, specifically designed for a graph with 5 nodes. It defines a Node class to represent each city and its connections, and includes methods for initializing nodes and calculating the shortest paths from a starting node. The algorithm processes nodes based on their adjacency information and path costs, ultimately aiming to reach a designated goal node while handling cases of limited search.

Uploaded by

Vincent Azuka
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd

/*

* Click nbfs://nbhost/SystemFileSystem/Templates/Licenses/[Link] to
change this license
* Click nbfs://nbhost/SystemFileSystem/Templates/Classes/[Link] to edit this
template
*/

/**
*
* azuka bee
*/
//This is a greedy incomplete (does not find solution for all types of connected
graphs)
import [Link].*;
public class ShortestPathGreedy {
public static int N = 5;
public static int adjInfoAll[][] = new int[N][N];// Storing Adjacency Info for
all cities
public static int weightToSource[]= new int[N],pathCost=0;// Storing Adjacency
Info for all cities
static int parents[] = new int[N];
public static class Node
{
int weightInfo[] = new int[N],id;// storing adjacency info for a node
(city)
int adjInfo[] = new int[N];// storing adjacency info for a node (city)
int parent;// storing parent of node
char status;//w (white) new or g (grey) processed
}
public static int getDistance(int id){
return weightToSource[id];
}
// Method for allocating a new node
public static Node newNode(int id,int parent){

Node node1 = new Node();


[Link] = parent;//setting pointer from the path to the root
[Link]='w';
[Link]=id;

return node1;
}
//For a connected Graph, starting from s=0
public static void shortestPaths(int adjInfoAll[][],int s){
int count=0;
Node start = newNode(s,-1);
//[Link]=-1;
parents[[Link]]=-1;//This node has no parent
Node min1=start;
int smallId=0,small=100;//10000 is infinite here
[Link]("The path is: (Path Cost is in bracket)");
[Link]([Link]+" ->");
while(true){
if([Link]==[Link])
weightToSource[[Link]]=0;
[Link]='g';
for(int j=0;j<5;j++){
if(adjInfoAll[[Link]][j]!=0&&adjInfoAll[[Link]]
[j]<small&&parents[j]==-2){
small=adjInfoAll[[Link]][j];
smallId=j;
}
}
Node BestFringe = newNode(smallId,[Link]);
parents[smallId]=[Link];
weightToSource[[Link]]=pathCost+adjInfoAll[[Link]]
[[Link]];
pathCost+=adjInfoAll[[Link]][[Link]];
if([Link]==4){//Goal node is reached
[Link]([Link]+" ( "+pathCost+" )");
break;
}
else
[Link]([Link]+" ( "+pathCost+" )->");
min1=BestFringe;
if(++count==15){
[Link]("Limit of search reached, either no route or bad
path used");
break;
}
}

}
public static void main(String args[]){
for(int j=0;j<5;j++)
parents[j]=-2;//Meaning the node has not been seen yet.
/* Node 0(A) connects to Node 1(B) with a cost of 2
Node 0(A) connects to Node 2(C) with a cost of 3
Node 0(A) connects to Node 3(D) with a cost of 4
Node 1(B) connects to Node 4(E) with a cost of 1
Node 2(C) connects to Node 4(E) with a cost of 2
Node 3(D) connects to Node 4(E) with a cost of 6
*/
int initialM[][] =
{
{0, 2, 3, 4, 100},
{2, 0, 100, 100, 1},
{3, 100, 0, 100, 2},
{4, 100, 100, 0, 6},
{100, 1, 2, 6, 0}
};
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
adjInfoAll[i][j]=initialM[i][j];
//If you want a different start and end nodes, then rearrange the id with
start node 0 and end node n-1
shortestPaths(adjInfoAll,0);
}

You might also like