为什么我不能（for）循环我的图形节点和边缘的输入？

Question

这是我的代码：

import java.util.*;

public class Dijkstra {

// 1 = A
// 2 = B
// 3 = C
// 4 = D
// 5 = E
// 6 = F
// 7 = G
// 8 = H

private static final Graph.Edge[] GRAPH = null;

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    Graph.Edge[] GRAPH = { 
            new Graph.Edge(sc.next(), sc.next(), sc.nextInt()),
            new Graph.Edge(sc.next(), sc.next(), sc.nextInt()),
            new Graph.Edge(sc.next(), sc.next(), sc.nextInt()),
            new Graph.Edge(sc.next(), sc.next(), sc.nextInt()),
            new Graph.Edge(sc.next(), sc.next(), sc.nextInt()),
            new Graph.Edge(sc.next(), sc.next(), sc.nextInt()),
            new Graph.Edge(sc.next(), sc.next(), sc.nextInt()),
            new Graph.Edge(sc.next(), sc.next(), sc.nextInt())
            };

    String START = sc.next();
    String END = sc.next();
    Graph g = new Graph(GRAPH);
    g.dijkstra(START);
    // print the shortest path using Dijkstra algorithm
    g.printPath(END);
    // g.printAllPaths();
    }
}

class Graph {
    public static Map<String, Vertex> graph; // mapping of vertex names to 
Vertex objects, built from a set of Edges

/** One edge of the graph (only used by Graph constructor) */
public static class Edge {
    public String v1, v2;
    public int dist;

    public Edge(String v1, String v2, int dist) {
        this.v1 = v1;
        this.v2 = v2;
        this.dist = dist;
    }
}

/** One vertex of the graph, complete with mappings to neighbouring vertices */
public static class Vertex implements Comparable<Vertex> {
    public String name;
    public int dist = Integer.MAX_VALUE; // MAX_VALUE assumed to be infinity
    public Vertex previous = null;
    public Map<Vertex, Integer> neighbours = new HashMap<Vertex, Integer>();

    public Vertex(String name) {
        this.name = name;
    }

    public void printPath() {
        if (this == this.previous) {
            System.out.println(this.name);
        } else if (this.previous == null) {
            System.out.printf("%s(unreached)", this.name);
        } else {
            this.previous.printPath();
            System.out.println(this.name);
        }
    }

    public int compareTo(Vertex other) {
        if (dist == other.dist)
            return name.compareTo(other.name);
        return Integer.compare(dist, other.dist);
    }
}

/** Builds a graph from a set of edges */
public Graph(Edge[] edges) {
    graph = new HashMap<String, Vertex>(edges.length);

    // one pass to find all vertices
    for (Edge e : edges) {
        if (!graph.containsKey(e.v1))
            graph.put(e.v1, new Vertex(e.v1));
        if (!graph.containsKey(e.v2))
            graph.put(e.v2, new Vertex(e.v2));
    }

    // another pass to set neighbouring vertices
    for (Edge e : edges) {
        graph.get(e.v1).neighbours.put(graph.get(e.v2), e.dist);
        graph.get(e.v2).neighbours.put(graph.get(e.v1), e.dist); // also do this for an undirected graph
    }
}

/** Runs dijkstra using a specified source vertex */
public void dijkstra(String startName) {
    if (!graph.containsKey(startName)) {
        System.err.printf("Graph doesn't contain start vertex \"%s\"\n", startName);
        return;
    }
    final Vertex source = graph.get(startName);
    NavigableSet<Vertex> q = new TreeSet<Vertex>();

    // set-up vertices
    for (Vertex v : graph.values()) {
        v.previous = v == source ? source : null;
        v.dist = v == source ? 0 : Integer.MAX_VALUE;
        q.add(v);
    }

    dijkstra(q);
}

/** Implementation of dijkstra's algorithm using a binary heap. */
private void dijkstra(final NavigableSet<Vertex> q) {
    Vertex u, v;
    while (!q.isEmpty()) {

        u = q.pollFirst(); // vertex with shortest distance (first iteration will return source)
        if (u.dist == Integer.MAX_VALUE)
            break; // we can ignore u (and any other remaining vertices) since they are unreachable

        // look at distances to each neighbour
        for (Map.Entry<Vertex, Integer> a : u.neighbours.entrySet()) {
            v = a.getKey(); // the neighbour in this iteration

            final int alternateDist = u.dist + a.getValue();
            if (alternateDist < v.dist) { // shorter path to neighbour found
                q.remove(v);
                v.dist = alternateDist;
                v.previous = u;
                q.add(v);
            }
        }
    }
}

/** Prints a path from the source to the specified vertex */
public void printPath(String endName) {
    if (!graph.containsKey(endName)) {
        System.err.printf("Graph doesn't contain end vertex \"%s\"\n", endName);
        return;
    }

    graph.get(endName).printPath();
}

/**
 * Prints the path from the source to every vertex (output order is not
 * guaranteed)
 */
public void printAllPaths() {
    for (Vertex v : graph.values()) {
        v.printPath();
        }
    }
}

在我的主要方法中，我尝试循环输入图形：

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Graph.Edge[] GRAPH = { 
                new Graph.Edge(sc.next(), sc.next(), sc.nextInt()),
                new Graph.Edge(sc.next(), sc.next(), sc.nextInt()),
                new Graph.Edge(sc.next(), sc.next(), sc.nextInt()),
                new Graph.Edge(sc.next(), sc.next(), sc.nextInt()),
                new Graph.Edge(sc.next(), sc.next(), sc.nextInt()),
                new Graph.Edge(sc.next(), sc.next(), sc.nextInt()),
                new Graph.Edge(sc.next(), sc.next(), sc.nextInt()),
                new Graph.Edge(sc.next(), sc.next(), sc.nextInt())
                };

        String START = sc.next();
        String END = sc.next();
        Graph g = new Graph(GRAPH);
        g.dijkstra(START);
        // print the shortest path using Dijkstra algorithm
        g.printPath(END);
        // g.printAllPaths();
    }

所以我试图让它像这样循环，在这里我可以循环图形输入 n 次。但是，每当我这样做时，都会出现问题

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    for(int i = 0; i < n; i++) {
        Graph.Edge[] GRAPH = {
            new Graph.Edge(sc.next(),sc.next(),sc.nextInt())
        };
    }

错误是：

Exception in thread "main" java.lang.NullPointerException
at Graph.<init>(Dijkstra.java:80)
at Dijkstra.main(Dijkstra.java:26)

我想知道问题是什么，以及问题的解决方案。

Answer 1

我发现没有问题，因为我使用两种情况测试了您的代码，分别是从静态数据和控制台输入构建的。

以下是我的案例处理方法：

private static final Graph.Edge[] buildData()
{
    Graph.Edge[] GRAPH = { 
        new Graph.Edge("A", "B", 5),
        new Graph.Edge("C", "D", 7), 
        new Graph.Edge("E", "F", 3),
        new Graph.Edge("G", "H", 2), 
        new Graph.Edge("B", "C", 1),
        new Graph.Edge("D", "E", 9), 
        new Graph.Edge("A", "H", 4),
        new Graph.Edge("G", "B", 6) 
    };

    return GRAPH;
}

和两种方法。

public static void main_build(String[] args) {
    String START = "A";
    String END = "G";
    Graph.Edge[] GRAPH = buildData();
    Graph g = new Graph(GRAPH);

    g.dijkstra(START);
    // print the shortest path using Dijkstra algorithm
    g.printPath(END);
    //g.printAllPaths();
}

public static void main_input(String[] args) {
    Scanner sc = new Scanner(System.in);
    //int n = sc.nextInt();
    //
    Graph.Edge[] GRAPH = { 
        new Graph.Edge(sc.next(), sc.next(), sc.nextInt()),
        new Graph.Edge(sc.next(), sc.next(), sc.nextInt()), 
        new Graph.Edge(sc.next(), sc.next(), sc.nextInt()),
        new Graph.Edge(sc.next(), sc.next(), sc.nextInt()), 
        new Graph.Edge(sc.next(), sc.next(), sc.nextInt()),
        new Graph.Edge(sc.next(), sc.next(), sc.nextInt()), 
        new Graph.Edge(sc.next(), sc.next(), sc.nextInt()),
        new Graph.Edge(sc.next(), sc.next(), sc.nextInt()) 
    };

    String START = sc.next();
    String END = sc.next();
    Graph g = new Graph(GRAPH);

    g.dijkstra(START);
    // print the shortest path using Dijkstra algorithm
    g.printPath(END);
    // g.printAllPaths();

    sc.close();
    sc = null;
}

第二种方法的按键输入，main_input必须是，

A B 5 C D 7 E F 3 G H 2 B C 1 D E 9 A H 4 G B 6 A G

关于for循环语句，和我之前介绍的方法是一样的

这是一个for循环方法，你的 for 循环语句看起来像；

public static void main_forloop(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    Graph.Edge[] GRAPH = new Graph.Edge[n];

    for(int i = 0; i < n; i++) {
        GRAPH[i] = 
            new Graph.Edge(sc.next(),sc.next(),sc.nextInt());
    }

    String START = sc.next();
    String END = sc.next();
    Graph g = new Graph(GRAPH);

    g.dijkstra(START);
    // print the shortest path using Dijkstra algorithm
    g.printPath(END);
    // g.printAllPaths();

    sc.close();
    sc = null;
}

控制台输入为：

8 A B 5 C D 7 E F 3 G H 2 B C 1 D E 9 A H 4 G B 6 A G

你可以在eclipse环境下用下面的控制台输出图像与你的进行比较。

关于dijkstra算法的文章太多了。我认为这不是程序问题而是测试数据。

我发现这个网站有测试数据文件。

Shortest Paths

您可以使用站点中的数据测试您的代码 - 您需要使用 java 中的文件流类从文件构建数据。

希望对您有所帮助。

为什么我不能（for）循环我的图形节点和边缘的输入？

How come I cannot (for) loop the input for my Graph's nodes and edges?

java

for-loop

graph

dijkstra