Pregunta
I'm trying to write a form a Dijkstra’s algorithm, with the weight between two vertices the distance between a set of coordinates taken in from a file. It adds the Vertices fine but when it goes to add in the edges I'm getting a null pointer in my main method.
https://stackoverflow.com/questions/23291731
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianException in thread "main" java.lang.NullPointerException
at matrix.matrix(matrix.java:61)
at matrix.main(matrix.java:102)
Which point to the marked(**) parts of code. It's probably something really simple that I'm missing so any help would be greatly appreciated! Thanks.
import java.util.*;
import java.io.*;
class matrix
{
//public static double[][] distanceMatrix;
public static int[] nameOfCities;
public static double[] Latitude;
public static double[] Longitude;
public static Graph theGraph = new Graph();
public static void matrix()
{
int size=0;
try {
File f = new File("Cities2.txt");//the file where the coordinates of cities are kept
Scanner sc = new Scanner(f);
Scanner scan = new Scanner(f);
int i=0;
while(scan.hasNextLine())
{
String readLine = scan.nextLine();
size++;
}
System.out.println("The number of cities is "+size);
double[] Latitude = new double[size];
double[] Longitude = new double[size];
nameOfCities = new int[size];
//double[][] distanceMatrix = new double[size][size];
while(sc.hasNextLine())
{
String line = sc.nextLine();
String[] details = line.split(" ");//until there's a space(" ") in the file
int name = Integer.parseInt(details[0]);//number in the file corresponds to the name of the town
nameOfCities[i]=name;//add this to the array called nameOfCities
double latitude = Double.parseDouble(details[1]);//corresponds to latitude value
Latitude[i]=latitude;//add this to latitude array
double longitude = Double.parseDouble(details[2]);//corresponds to longitude array
Longitude[i]=longitude;//add this to longitude array
theGraph.addVertex(i+1);
theGraph.displayVertex(i);
System.out.println(" Vertex added");
i++;
}
}
catch (FileNotFoundException e)
{
e.printStackTrace();
}
**for(int i=0; i<Latitude.length; i++)**
{
for(int j=i; j<Longitude.length; j++)
{
double distance = getDistance(Latitude[i],Longitude[i],Latitude[j],Longitude[j]);//gets distance between two points
distance = (double)Math.round(distance*100000.0)/100000.0;
//distanceMatrix[i][j] = distance;//inserts it into the matrix
theGraph.addEdge(i,j,distance);
System.out.print("Edge added.");
}
}
System.out.print("Distance matrix and graph filled.");//matrix is filled
}
public static double getDistance(double lat1, double lon1, double lat2, double lon2)
{
//gets the distance using haversine function
double R = 6371;
double dLat = Math.toRadians((lat2-lat1));
double dLon = Math.toRadians((lon2-lon1));
double a = Math.sin(dLat/2) * Math.sin(dLat/2) +
Math.cos(Math.toRadians(lat1)) * Math.cos(Math.toRadians(lat2)) *
Math.sin(dLon/2) * Math.sin(dLon/2);
double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));
double d = R * c;
return d;
}
public static void main(String[] args)
{
System.out.println("Filling Graph...");
**matrix();**
System.out.print("Shortest paths: ");
theGraph.path(); //shortest paths
System.out.println();
} // end main()
}
And here's my graph class
class Graph
{
private final int MAX_VERTS = 80;
private final int INFINITY = 1000000;
private Vertex vertexList[]; // list of vertices
private double adjMat[][]; // adjacency matrix
private int nVerts; // current number of vertices
private int nTree; //number of verts in tree
private DistPar sPath[]; //array for shortest-path data
private int currentVert;
private PriorityQ thePQ;
private double startToCurrent; //distance to currentVert
// -------------------------------------------------------------
public Graph() // constructor
{
vertexList = new Vertex[MAX_VERTS];
// adjacency matrix
adjMat = new double[MAX_VERTS][MAX_VERTS];
nVerts = 0;
nTree=0;
for(int j=0; j<MAX_VERTS; j++) // set adjacency
for(int k=0; k<MAX_VERTS; k++) // matrix to 0
adjMat[j][k] = INFINITY;
thePQ = new PriorityQ();
sPath = new DistPar[MAX_VERTS]; // shortest paths
} // end constructor
// -------------------------------------------------------------
public void addVertex(int lab)
{
vertexList[nVerts++] = new Vertex(lab);
}
// -------------------------------------------------------------
public void addEdge(int start, int end, double weight)
{
adjMat[start][end] = weight;
adjMat[end][start] = weight;
}
// -------------------------------------------------------------
public void displayVertex(int v)
{
System.out.print(vertexList[v].label);
}
// -------------------------------------------------------------
public void mstw() // minimum spanning tree
{
currentVert = 0; // start at 0
while(nTree < nVerts-1) // while not all verts in tree
{ // put currentVert in tree
vertexList[currentVert].isInTree = true;
nTree++;
// insert edges adjacent to currentVert into PQ
for(int j=0; j<nVerts; j++) // for each vertex,
{
if(j==currentVert) // skip if it’s us
continue;
if(vertexList[j].isInTree) // skip if in the tree
continue;
double distance = adjMat[currentVert][j];
if( distance == INFINITY) // skip if no edge
continue;
putInPQ(j, distance); // put it in PQ (maybe)
}
if(thePQ.size()==0) // no vertices in PQ?
{
System.out.println(" GRAPH NOT CONNECTED");
return;
}
// remove edge with minimum distance, from PQ
Edge theEdge = thePQ.removeMin();
int sourceVert = theEdge.srcVert;
currentVert = theEdge.destVert;
// display edge from source to current
System.out.print( vertexList[sourceVert].label );
System.out.print( vertexList[currentVert].label );
System.out.print(" ");
} // end while(not all verts in tree)
// mst is complete
for(int j=0; j<nVerts; j++) // unmark vertices
vertexList[j].isInTree = false;
} // end mstw
// -------------------------------------------------------------
public void putInPQ(int newVert, double newDist)
{
// is there another edge with the same destination vertex?
int queueIndex = thePQ.find(newVert);
if(queueIndex != -1) // got edge’s index
{
Edge tempEdge = thePQ.peekN(queueIndex); // get edge
double oldDist = tempEdge.distance;
if(oldDist > newDist) // if new edge shorter,
{
thePQ.removeN(queueIndex); // remove old edge
Edge theEdge = new Edge(currentVert, newVert, newDist);
thePQ.insert(theEdge); // insert new edge
}
// else no action; just leave the old vertex there
} // end if
else // no edge with same destination vertex
{ // so insert new one
Edge theEdge = new Edge(currentVert, newVert, newDist);
thePQ.insert(theEdge);
}
} // end putInPQ()
// -------------------------------------------------------------
public void path() // find all shortest paths
{
int startTree = 0; // start at vertex 0
vertexList[startTree].isInTree = true;
nTree = 1; // put it in tree
// transfer row of distances from adjMat to sPath
for(int j=0; j<nVerts; j++)
{
double tempDist = adjMat[startTree][j];
sPath[j] = new DistPar(startTree, tempDist);
}
// until all vertices are in the tree
while(nTree < nVerts)
{
int indexMin = getMin(); // get minimum from sPath
double minDist = sPath[indexMin].distance;
if(minDist == INFINITY) // if all infinite
{ // or in tree,
System.out.println("There are unreachable vertices");
break; // sPath is complete
}
else
{ // reset currentVert
currentVert = indexMin; // to closest vert
startToCurrent = sPath[indexMin].distance;
// minimum distance from startTree is
// to currentVert, and is startToCurrent
}
// put current vertex in tree
vertexList[currentVert].isInTree = true;
nTree++;
adjust_sPath(); // update sPath[] array
} // end while(nTree<nVerts)
displayPaths(); // display sPath[] contents
nTree = 0; // clear tree
for(int j=0; j<nVerts; j++)
vertexList[j].isInTree = false;
} // end path()
public int getMin() // get entry from sPath
{ // with minimum distance
double minDist = INFINITY; // assume large minimum
int indexMin = 0;
for(int j=1; j<nVerts; j++) // for each vertex,
{ // if it’s in tree and
if( !vertexList[j].isInTree && // smaller than old one
sPath[j].distance < minDist )
{
minDist = sPath[j].distance;
indexMin = j; // update minimum
}
} // end for
return indexMin; // return index of minimum
} // end getMin()
public void adjust_sPath()
{
// adjust values in shortest-path array sPath
int column = 1; // skip starting vertex
while(column < nVerts) // go across columns
{
// if this column’s vertex already in tree, skip it
if( vertexList[column].isInTree )
{
column++;
continue;
}
// calculate distance for one sPath entry
// get edge from currentVert to column
double currentToFringe = adjMat[currentVert][column];
// add distance from start
double startToFringe = startToCurrent + currentToFringe;
// get distance of current sPath entry
double sPathDist = sPath[column].distance;
// compare distance from start with sPath entry
if(startToFringe < sPathDist) // if shorter,
{ // update sPath
sPath[column].parentVert = currentVert;
sPath[column].distance = startToFringe;
}
column++;
} // end while(column < nVerts)
} // end adjust_sPath()
public void displayPaths()
{
for(int j=0; j<nVerts; j++) // display contents of sPath[]
{
System.out.print(vertexList[j].label + "="); // B=
if(sPath[j].distance == INFINITY)
System.out.print("inf"); // inf
else
System.out.print(sPath[j].distance); // 50
int parent = vertexList[ sPath[j].parentVert ].label;
System.out.print("(" + parent + ") "); // (A)
}
System.out.println("");
}
} // end class Graph
All the other classes involved just hold constructors and there's a priority queue class to try and implement the algorithm in a different way but I'm still getting the same null pointer. All suggestions welcome, even if I have to completely change my code!! :)
Solución
You're shadowing the variable Latitude (and Longitude)
double[] Latitude = new double[size];
should be
Latitude = new double[size];
Note: Java naming conventions suggest that variables start with a lowercase letter, e.g. latitude and longitude
