i am working in Dijkstra code.which i want to get the vertexes from user by using Array list.but there is a problem in computepath method i can't solve it.

public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        System.out.println("insert the number of Vertexes:");
        int nv=input.nextInt();//nv = number of vertexes
        Integer tmp;
         HashMap<String , Vertex> h = new HashMap<String , Vertex>();
        ArrayList <Vertex > a = new ArrayList<Vertex>();
        for(Integer i = 0 ; i < nv ; i++){
            String str;
            str  = "v"+Integer.toString(i);
            Vertex buff = new Vertex(str);
            //a[i] = new Vertex(str);
            a.add(buff);
            h.put(str, a.get(i));
            str = "" ;
        }

        for(int j = 0 ; j  < nv ; j++){
            System.out.println("enter the number of adjacencies of v"+j);
            int na=input.nextInt();//na = number of adjacencies
            for(int i = 0 ; i < na ; i++){
                String tmp2 = "";
                double wi = 0;
                System.out.println("enter the "+(i+1)+" th adjacence of v"+j+": ");
                String buff = input.nextLine();
                tmp2 = input.nextLine();
                System.out.println("enter the weight of this adjacencies:");
                wi = input.nextDouble();
                a.get(j).adjacencies = new edge []{
                    new edge(h.get(tmp2) , wi)
                };
            }
        }
         computePaths(a.get(0));
          System.out.println("pleas enter a vertex:");
          int x=input.nextInt();

compute path method is this

public static void computePaths(Vertex source)
      {
          source.minDistance = 0.;
          PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
  	vertexQueue.add(source);
  
  	while (!vertexQueue.isEmpty()) {
  	    Vertex u = vertexQueue.poll();
            
  
              // Visit each edge exiting u
             for (edge e : u.adjacencies)
              {
                  Vertex v = e.target;
                 double weight = e.weight;
                  double distanceThroughU = u.minDistance + weight;
  		if (distanceThroughU < v.minDistance) {
  		  vertexQueue.remove(v);  
                   
  		    v.minDistance = distanceThroughU ;
  		    v.previous = u;
  		  vertexQueue.add(v);
  
  		}  
  
              }
        }}

there is a problem in computepath method

Please explain. Show what the code is currently doing and explain what is wrong with that and show what it should be doing.

Please explain. Show what the code is currently doing and explain what is wrong with that and show what it should be doing

before using this kind of way the dijkstra codes used this in the main part

Vertex v0 = new Vertex("v0");
 	Vertex v1 = new Vertex("v1");
 	Vertex v2 = new Vertex("v2");
 	Vertex v3 = new Vertex("v3");
 	Vertex v4 = new Vertex("v4");
 	Vertex v5 = new Vertex("v5");
 	Vertex v6 = new Vertex("v6");
 	v0.adjacencies = new edge[]{ new edge(v1,  79.83),
 	                             new edge(v5,  81.15) };
 	v1.adjacencies = new edge[]{ new edge(v0,  79.75),
 	                             new edge(v2,  39.42),
 	                             new edge(v3, 103.00) };
 	v2.adjacencies = new edge[]{ new edge(v1,  38.65) };
 	v3.adjacencies = new edge[]{ new edge(v1, 102.53),
 	                             new edge(v5,  61.44),
 	                             new edge(v6,  96.79) };
 	v4.adjacencies = new edge[]{ new edge(v5, 133.04) };
 	v5.adjacencies = new edge[]{ new edge(v0,  81.77),
 	                             new edge(v3,  62.05),
 	                             new edge(v4, 134.47),
 	                             new edge(v6,  91.63) };
 	v6.adjacencies = new edge[]{ new edge(v3,  97.24),
 	                             new edge(v5,  87.94) };
 	Vertex[] vertices = { v0, v1, v2, v3, v4, v5, v6 };

it want to get Vertexes and their adjacncies from user.instead of writting them in the main method.

after getting information from user the error below apears:

Exception in thread "main" java.lang.NullPointerException
at dijkstra.Dijkstra.computePaths(Dijkstra.java:31)
at dijkstra.Dijkstra.main(Dijkstra.java:133)
Java Result: 1

Edited 4 Years Ago by behrad kiani: n/a

Exception in thread "main" java.lang.NullPointerException
at dijkstra.Dijkstra.computePaths(Dijkstra.java:31)

Look at line 31 in Dijkstra.java and see what variable has a null value. Then backtrack in the code to see why that variable does not have a valid value.

i wrote down the whole program except of Vertex class

package dijkstra;
  import java.util.PriorityQueue;

  
  import java.util.List;

  import java.util.ArrayList;

  import java.util.Collections;

 

	import java.util.*;

	public class Dijkstra{

	 
	 
      public static void computePaths(Vertex source)
      {
          source.minDistance = 0.;
          PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
  	vertexQueue.add(source);
  
  	while (!vertexQueue.isEmpty()) {
  	    Vertex u = vertexQueue.poll();
            
  
              // Visit each edge exiting u
             for (edge e : u.adjacencies)
              {
                  Vertex v = e.target;
                 double weight = e.weight;
                  double distanceThroughU = u.minDistance + weight;
  		if (distanceThroughU < v.minDistance) {
  		  vertexQueue.remove(v);  
                   
  		    v.minDistance = distanceThroughU ;
  		    v.previous = u;
  		  vertexQueue.add(v);
  
  		}  
  
              }
        }}
  
  
     public static List<Vertex> getShortestPathTo(Vertex target)
      {
          List<Vertex> path = new ArrayList<Vertex>();
          for (Vertex ver = target; ver != null; ver = ver.previous)
              path.add(ver);
  
         Collections.reverse(path);
          return path;
      }
  


    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        System.out.println("insert the number of Vertexes:");
        int nv=input.nextInt();//nv = number of vertexes
        Integer tmp;
         HashMap<String , Vertex> h = new HashMap<String , Vertex>();
       
        ArrayList <Vertex > a = new ArrayList<Vertex>();
        
        for(Integer i = 0 ; i < nv ; i++){
            String str;
            str  = "v"+Integer.toString(i);
            Vertex buff = new Vertex(str);
            //a[i] = new Vertex(str);
            a.add(buff);
            h.put(str, a.get(i));
            
//            else{
//                h.put(str, a[i]);
//            }
            str = "" ;
        }

        for(int j = 0 ; j  < nv ; j++){
            System.out.println("enter the number of adjacencies of v"+j);
            int na=input.nextInt();//na = number of adjacencies
            for(int i = 0 ; i < na ; i++){
                String tmp2 = "";
                double wi = 0;
                System.out.println("enter the "+(i+1)+" th adjacence of v"+j+": ");
                String buff = input.nextLine();
                tmp2 = input.nextLine();
                System.out.println("enter the weight of this adjacencies:");
                wi = input.nextDouble();
                a.get(j).adjacencies = new edge []{
                    new edge(h.get(tmp2) , wi)
                };
                //a[j].adjacencies = new edge []{
                  //  new edge(h.get(tmp2) , wi)};

                
            }
        }

         computePaths(a.get(0));
          System.out.println("pleas enter a vertex:");
          int x=input.nextInt();
          
 	
 	    System.out.println("Distance to " + a.get(x) + ": " + a.get(x).minDistance);
 	    List<Vertex> path = getShortestPathTo(a.get(x));
 	    System.out.println("Path: " + path);
 	
 
     }
 }

One way to find it is to add a println statement just before the statement where the exception occurs and print out the values of all the variables used on the line with the exception. Then you can see which one it is.

One way to find it is to add a println statement just before the statement where the exception occurs and print out the values of all the variables used on the line with the exception. Then you can see which one it is.

you know i tried the things you said in the other way but i think it has logical problem with adjacencies.i would be glad if you find that one's problem.the logical problem apears here in this line of code

for (edge e : u.adjacencies)

Have you found the variable with the null value and fixed the code?

What is the value of: u.adjacencies
did you print it out to see if it was null?

Edited 4 Years Ago by NormR1: n/a

This article has been dead for over six months. Start a new discussion instead.