New Topic/Question
Reply
I wrote 3 classes Vertex, Edge and Main classes. in the main i get the user input and create and array of vertcies and add the vertcies then added the edges to each vertex.
2 // # of test cases
n m s t
2 1 0 1 // case #1
0 1 100
Case #1: 100
3 3 2 0 // case #2
0 1 100
0 2 200
1 2 50
Case #2: 150
The problem is that in line 108 i get an error saying null pointer exception.
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main {
static class Vertex implements Comparable<Vertex>
{
public int name, curIndex;
public Edge[] adjacencies;
public double minDistance = Double.POSITIVE_INFINITY;
public Vertex previous;
public Vertex(int argName) { name = argName; }
public int compareTo(Vertex other)
{
return Double.compare(minDistance, other.minDistance);
}
}
static class Edge
{
public Vertex target;
public double weight;
public Edge(Vertex argTarget, double argWeight)
{ target = argTarget; weight = argWeight; }
}
public static void main(String[] args) {
// TODO code application logic here
int uIn,n,m,S,T,N,W,v1,v2,length;
int uInArray []= new int [ 4 ];
int[] uInArray1 = new int [ 3 ];
Scanner s = new Scanner(System.in);
Vertex ver,u,v;
v = new Vertex(100);
u = new Vertex(101);
Edge ed = null;
Vertex[] verArray;
PriorityQueue<Vertex> pq;
uIn = s.nextInt();
N = uIn;
for(int i = 0; i < N; i++)
{
for(int c = 0; c <= 3; c++)
{
uIn = s.nextInt();
uInArray[ c ] = uIn;
} //getting n,m,s,t
n = uInArray [ 0 ];//input
m = uInArray [ 1 ];//input
S = uInArray [ 2 ];//input
T = uInArray [ 3 ];//input
verArray = new Vertex [ n ];
for(int z = 0; z < n; z++)
{
ver = new Vertex( z );
ver.curIndex = 0;
verArray [ z ] = ver;
verArray [ z ]. adjacencies = new Edge [ 3 ];
}//creating vertices and adding them to the array and add array of edges to the array of array of edges
for(int b = 0; b < m; b++)
{
for(int k = 0 ; k < 3; k++)
{
uIn = s.nextInt();
uInArray1 [ k ] = uIn;
}
v1 = uInArray1[ 0 ];//input
v2 = uInArray1[ 1 ];//input
W = uInArray1 [ 2 ];//input
ed = new Edge(verArray [ v1 ] , W );
verArray[ v2 ]. adjacencies [ verArray[ v2 ].curIndex ] = ed;//adding the edge in the array of edges of the vertex
verArray[ v2 ].curIndex = verArray[ v2 ].curIndex + 1;//incrementing the index of the array of edges
//so if i am going to add another edge to this vertex
//it is added in the next index and do not overwite the prev.
ed = new Edge(verArray [ v2 ] , W );
verArray[ v1 ] . adjacencies [ verArray [ v1 ].curIndex ] = ed;//adding the edge in the array of edges of the vertex
verArray[ v1 ].curIndex = verArray[ v1 ].curIndex + 1;//incrementing the index of the array of edges
//so if i am going to add another edge to this vertex
//it is added in the next index and do not overwite the prev.
}
verArray[ S ].previous = null;
verArray[ S ].minDistance = 0.0;
pq = new PriorityQueue<Vertex>();
pq.add( verArray[ S ] );
while(!pq.isEmpty())
{
u = pq.poll();
for(int g = 0; g < u.adjacencies.length; g++)
{
System.out.println("weight"+u.adjacencies[ g ].weight);//test
System.out.println("u min"+u.minDistance);//test
System.out.println("v min"+v.minDistance);//test
if((u.adjacencies[ g ].weight + u.minDistance) < v.minDistance)
{
v.previous = u;
v.minDistance = u.adjacencies[ g ].weight + u.minDistance;
pq.add(v);
}
}
}
System.out.println("case " + ( i + 1 ) + " : " + verArray [ T ].minDistance);
}
}
}
thanks
This post has been edited by kngofdrkns: 01 December 2010 - 08:57 AM
MultiQuote
| 