java - 对这段代码感到困惑。迪杰斯特拉算法

Question

重新编辑:抱歉，如果我将代码粘贴到pastebin。我不知道你们能这么快结束问题。

所以我正在修改代码，完成后我不知道为什么我做错了，因为:

Everytime I add a entry in the map file It instead of calculating the the path It returns infinity on the eigth node: It doesnt give a stack trace but instead it throws:

Distance to Mandurriao: 0.0
Path: [Mandurriao]
Distance to Jaro: 79.0
Path: [Mandurriao, Jaro]
Distance to Iloilo: 118.0
Path: [Mandurriao, Jaro, Iloilo]
Distance to Leganes: 182.0
Path: [Mandurriao, Jaro, Leganes]
Distance to Tagbak: 81.0
Path: [Mandurriao, Tagbak]
Distance to Derp: 214.0
Path: [Mandurriao, Tagbak, Derp]
Distance to Herp: 305.0
Path: [Mandurriao, Tagbak, Derp, Herp]
Distance to Tugigarao: Infinity
Path: [Tugigarao]

And everytime I make my map file less than 7 nodes it gives me:

Exception in thread "main" java.lang.NullPointerException
        at Dijkstra.search(Dijkstra.java:81)
        at Dijkstra.main(Dijkstra.java:132)

我是一个彻头彻尾的java菜鸟，一天前我只是在写java代码。

所以这是代码:

import java.util.PriorityQueue;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
import java.io.*;
import java.util.*;

class Vertex implements Comparable<Vertex>
{
    public final String name;
    public Edge[] adjacencies;
    public double minDistance = Double.POSITIVE_INFINITY;
    public Vertex previous;
    public Vertex(String argName) { name = argName; }
    public String toString() { return name; }
    public int compareTo(Vertex other)
    {
        return Double.compare(minDistance, other.minDistance);
    }

}


class Edge
{
    public final Vertex target;
    public final double weight;
    public Edge(Vertex argTarget, double argWeight)
    { target = argTarget; weight = argWeight; }
}



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 vertex = target; vertex != null; vertex = vertex.previous)
            path.add(vertex);

        Collections.reverse(path);
        return path;
    }




     ///////////////////////////////////////////////////////////////////////////

    public static int search(String [ ] numbers, String key)
    {
           for (int index = 0; index < numbers.length; index++)
          {
               if ( numbers[index].equals(key) )
                     return index;  //We found it!!!
          }
         // If we get to the end of the loop, a value has not yet
         // been returned.  We did not find the key in this array.
         return -1;
    }

    ///////////////////////////////////////////////////////////////////////
    public static void main(String[] args)
    {
        int MapLength = 0;
        Vertex[] v = new Vertex[100];
        String[] names = new String[100];
        System.out.println("Initalized");
        try {
            int i = 0;
            System.out.println("Initalized[0]");
            FileInputStream fStream = new FileInputStream("f:\\map2.txt");
            System.out.println("Initalized[1]");
            BufferedReader in = new BufferedReader(new InputStreamReader(fStream));
            System.out.println("Initalized[2]");
            while (in.ready()) {
                String parsed = "";
                parsed = in.readLine();
                String[] t = parsed.split(">");
                if(t[0].equals("v")){
                    System.out.println("Added>" + parsed);
                    v[i] = new Vertex(t[1]);
                    names[i] = t[1];
                    i++;
                    MapLength = i;
                    }

                if(t[0].equals("e")){
                    System.out.println("Initalized[3]");
                    int a;
                    int weight;
                    int ii = 0;

                    System.out.println("Initalized[4]." + t[1]);
                    String[] container = t[1].split("-");
                    System.out.println("Initalized[5]." + container);

                    Edge[] temp = new Edge[(container.length - 1) / 2];


                    for(a = 1; a < container.length; a +=2 ){
                        System.out.println("Initalized[6]." + names[search( names , container[ a ] )] + "...." + Integer.parseInt(container[ a + 1 ]));
                        temp[ii] = new Edge(v[ search( names , container[ a ] ) ], Integer.parseInt(container[ a + 1 ]));
                        ii++;
                        }
                    //System.out.println("Debug@LineCurrentNumberSearch: " +  search( names , container[ a ] ) );
                    v[ search( names , container[ 0 ] ) ].adjacencies = temp;


                    }


            }
            in.close();
        } catch (IOException e) {
            System.out.println("File input error" + e);
            }

/*
    v[0] = new Vertex("Harrisburg");
    v[1] = new Vertex("Baltimore");
    v[2] = new Vertex("Washington");
    v[3] = new Vertex("Philadelphia");
    v[4] = new Vertex("Binghamton");
    v[5] = new Vertex("Allentown");
    v[6] = new Vertex("New York");



    v[0].adjacencies = new Edge[]{ new Edge(v[1],  79.83), new Edge(v[5],  81.15) };

    v[1].adjacencies = new Edge[]{ new Edge(v[0],  79.75),
                                 new Edge(v[2],  39.42),
                                 new Edge(v[3], 103.00) };
    v[2].adjacencies = new Edge[]{ new Edge(v[1],  38.65) };
    v[3].adjacencies = new Edge[]{ new Edge(v[1], 102.53),
                                 new Edge(v[5],  61.44),
                                 new Edge(v[6],  96.79) };
    v[4].adjacencies = new Edge[]{ new Edge(v[5], 133.04) };
    v[5].adjacencies = new Edge[]{ new Edge(v[0],  81.77),
                                 new Edge(v[3],  62.05),
                                 new Edge(v[4], 134.47),
                                 new Edge(v[6],  91.63) };
    v[6].adjacencies = new Edge[]{ new Edge(v[3],  97.24),
                                 new Edge(v[5],  87.94) };
*/

    Vertex[] vertices = new Vertex[MapLength];
    int j;
    for(j = 0; j < MapLength; j++){
        vertices[j] = v[j];
        }

        computePaths(v[0]);
        for (Vertex a : vertices)
    {
        System.out.println("Distance to " + a + ": " + a.minDistance);
        List<Vertex> path = getShortestPathTo(a);
        System.out.println("Path: " + path);
    }
    }
}

这是 map 文件:

v>Mandurriao
v>Jaro
v>Iloilo
v>Leganes
v>Tagbak
v>Derp
v>Herp
v>Tugigarao
e>Mandurriao-Jaro-79-Tagbak-81
e>Jaro-Mandurriao-79-Iloilo-39-Leganes-103
e>Iloilo-Jaro-38
e>Leganes-Jaro-102-Tagbak-61-Derp-69
e>Tagbak-Derp-133
e>Derp-Mandurriao-81-Leganes-62-Tagbak-134-Herp-91
e>Herp-Leganes-97-Derp-87
e>Tugigarao-Herp-100

有人可以帮助我吗？提前致谢。

Answer 1

如果输入文件包含以下条目:

v>Mandurriao
v>Jaro
v>Iloilo
v>Leganes
v>Tagbak
v>Derp
e>Mandurriao-Jaro-79-Tagbak-81
e>Jaro-Mandurriao-79-Iloilo-39-Leganes-103
e>Iloilo-Jaro-38
e>Leganes-Jaro-102-Tagbak-61-Derp-69
e>Tagbak-Derp-133

顶点“Derp”没有任何相邻顶点，因此u.adjacency为空，导致小于7的条目出现空指针异常。