java - Dijkstra 算法的文件输入

Question

我无法弄清楚如何使用 java 读取输入文件。该文件具有以下格式:

u1 v1 w1
u2 v2 w2
...
um vm wm
-1
source

每个三元组表示一条边，由其源顶点、目标顶点及其权重指定(例如:newyork boston 30)。该图的描述以“标志”(整数-1)结束。该标志后面有一个字符串；该字符串是 Dijkstra 最短路径算法的源顶点的名称。也就是说，您要确定并打印出从该源顶点到图中每个其他顶点的最短路径。这是我目前的工作。

import java.io.File;
import java.io.FileNotFoundException;
import java.util.PriorityQueue;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

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 ArrayList<Vertex> getShortestPathTo(Vertex target) {
        ArrayList<Vertex> path = new ArrayList<Vertex>();
        for (Vertex vertex = target; vertex != null; vertex = vertex.previous)
            path.add(vertex);

        Collections.reverse(path);
        return path;
    }

    public String[] readFile(String fileName) throws FileNotFoundException {
        Scanner input = new Scanner(new File(fileName));
        String line = "";
        while (input.hasNext()) {
            line = line.concat(input.nextLine());
        }
        String[] graph = line.split("");
        return graph;

    }

    public static void main(String[] args) throws FileNotFoundException {

        final String TEST = "/TestInput.txt";
        Scanner input = new Scanner(new File(TEST));
        String line = "";
        while (input.hasNext()) {
            line = line.concat(input.nextLine());
        }
        String[] graph = line.split(" ");

        for (int i = 0; i < graph.length; i++) {
            System.out.println(graph[i]);
        }

        Vertex[] verts = new Vertex[graph.length];
        Edge[] edges = new Edge[graph.length];
        Vertex v1 = new Vertex("");
        Vertex v2 = new Vertex("");
        Vertex source = new Vertex("");
        int count = 0;

        outerloop: for (int i = 0; i < (graph.length); i++) {

            if (graph[i].equals("-1")) {
                // do algorithm initialization here w/ source
            }
            if (i == 0) {
                verts[i] = new Vertex(graph[i]);
                count++;
            } else {
                innerloop: for (int j = count; j >= 0; j--) {
                    if (i / 3 == 0) {

                        if (graph[i].equals(verts[j].toString())) {
                            break innerloop;
                        } else if (j == 0) {
                            verts[count] = new Vertex(graph[i]);
                            v1 = verts[count];
                            count++;
                        }
                    }

                    if (i / 3 == 1) {

                        if (graph[i].equals(verts[j])) {
                            break innerloop;
                        } else if (j == 0) {
                            verts[count] = new Vertex(graph[i]);
                            v2 = verts[count];
                            count++;
                        }
                    }
                    if (i / 3 == 2) {

                    }
                }
            }

        }

        for (int i = 0; i < verts.length; i++) {
            System.out.println(verts[i]);
        }
    }
}

所以我唯一的问题是如何从给定的 .txt 文件格式转换为图表。欢迎提出任何建议。

Answer 1

使用 Scanner解析文件数据。对于每个元组，如果尚未创建源顶点，则创建它，否则在预先存在的图中找到它——创建一个搜索函数。对目标顶点执行相同的操作。接下来，创建一条权重等于元组中第三个标记的边，并将目标顶点添加到该边。最后，将边添加到源顶点的邻接表中。

对于前面提到的搜索功能，您可以实现从任意顶点开始搜索图的每个顶点的功能。递归是必要的。

public static Vertex search(Vertex src, String name);

一个更简单的解决方案是保留您在构建图形时创建的所有顶点的列表并对其进行搜索。

public static Vertex search(List<Vertex> vertices, String name);

当您完成图形的构建并且获得 Dijkstra 算法将开始的顶点的名称时，您可以使用搜索功能来获取对该顶点的引用。

Dijkstra.computePath(search(vertices, startVertexName));

而且，就是这样。以下是如何解析文件数据的示例:

List<Vertex> vertices = new ArrayList<Vertex>();
String src = 
    "Pittsburgh Philadelphia 323 "+
    "Pittsburgh Ohio 125 "+
    "Ohio Philadelphia 400 "+
    "-1 Ohio";
            //new Scanner(new File(fileName));
Scanner scnr = new Scanner(src); 
String src, target;
int weight;
while(scnr.hasNext())
{
    src = scnr.next();
    if(src.equals("-1"))
        break;
    else {
        target = scnr.next();
        weight = scnr.nextInt();
    }
    //call search(), implement logic in addToGraph()
    addVertexToGraph(src, target, weight, vertices);    
}   
String startVertexName = scnr.next();
scnr.close();

请注意Scanner.next返回由空格(默认分隔符)分隔的下一个标记，因此您的文件数据必须采用这种方式格式化。