使用有向图实现 Dijkstra 算法

Question

我正在尝试通过邻接表使用有向图来实现 Dijkstra 算法。我找到了一些我一直用作示例的示例代码。在该代码中，图形填充如下：

private static final Graph.Edge[] GRAPH = {
    new Graph.Edge("a", "b", 7),
    new Graph.Edge("a", "c", 9),
    new Graph.Edge("a", "f", 14),
    new Graph.Edge("b", "c", 10),
    new Graph.Edge("b", "d", 15),
    new Graph.Edge("c", "d", 11),
    new Graph.Edge("c", "f", 2),
   new Graph.Edge("d", "e", 6),
    new Graph.Edge("e", "f", 9),};
private static final String START = "a";
private static final String END = "e";

由于我需要从文本文件中的邻接列表进行填充，因此我尝试以这种方式进行：

List<Graph.Edge> list = new ArrayList<>();

    try {
        Scanner scanner = new Scanner(new File(filename));
        while (scanner.hasNextLine()) {
            String source = scanner.findInLine(NAME);
            if (source != null) {
                while (true) {
                    String to = scanner.findInLine(NAME);
                    if (to == null) {
                        break;
                    }
                    int weight = Integer.valueOf(scanner.findInLine(WEIGHT));
                    list.add(new Graph.Edge(source, to, weight));
                }
            }
            scanner.nextLine();
        }
    } catch (FileNotFoundException | NumberFormatException e) {
    }

和

static final Pattern NAME = Pattern.compile("\w+");
static final Pattern WEIGHT = Pattern.compile("\d+");

在示例代码中，他们然后运行 dijkstra 算法在图上按以下方式：

Graph g = new Graph(GRAPH);
    g.dijkstra(START);
    g.printPath(END);
    g.printAllPaths();

我尝试更新我的代码以适用于该算法的实现。我想到了以下内容：

try {
        Scanner scanner = new Scanner(new File(filename));

        while (scanner.hasNextLine()) {
            String source = scanner.findInLine(NAME);
            if (source != null) {
                while (true) {
                    String go = scanner.findInLine(NAME);
                    if (go == null) {
                        break;
                    }
                    int weight = Integer.valueOf(scanner.findInLine(WEIGHT));
                    Graph.Edge edge = new Graph.Edge(source, go, weight);

                    Graph g = new Graph(GRAPH);
                    g.dijkstra(source);
                    g.printPath(go);
                }
            }

            scanner.nextLine();
        }
    } catch (FileNotFoundException | NumberFormatException e) {
    }

当我尝试运行时，它似乎没有正确填充我的图表。它从 dijkstra 和 printPath 方法中产生错误，指出 "Graph doesn't contain start/end vertex." 我如何更新我的代码以便正确填充图形并能够正确实现算法？谢谢！

编辑：这是我的输入文件的示例

它遵循格式来源，adj。顶点，重量，调整。顶点、权重....

编辑 2：使用 Graph.Edge`

class Graph {

private final 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 final String v1, v2;
    public final int dist;

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

和

public Graph(Edge[] edges) {
    graph = new HashMap<>(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
    }
}

编辑：这是我从 http://rosettacode.org/wiki/Dijkstra%27s_algorithm#Java

中找到原始示例代码的地方

Answer 1

为了使用带有文件输入的应用程序，使用您的第一个文件输入算法。你的第二个算法是无用的，除非你想运行文件的每一行作为 Graph 只有一个 Vertex.

像这样使用你的代码（我已经在我更改的行上添加了注释）：

private static final Graph.Edge[] GRAPH = getEdges("input.txt"); // <-- CHANGED THIS
private static final String START = "1"; // <-- CHANGED THIS
private static final String END = "5"; // <-- CHANGED THIS

private static Graph.Edge[] getEdges(String fileName) { // <-- ADDED THIS
    final Pattern NAME = Pattern.compile("\w+");
    final Pattern WEIGHT = Pattern.compile("\d+");
    List<Graph.Edge> list = new ArrayList<>();
    try {
        Scanner scanner = new Scanner(new File(fileName));
        while (scanner.hasNextLine()) {
            String source = scanner.findInLine(NAME);
            if (source != null) {
                while (true) {
                    String to = scanner.findInLine(NAME);
                    if (to == null) {
                        break;
                    }
                    int weight = Integer.valueOf(scanner.findInLine(WEIGHT));
                    list.add(new Graph.Edge(source, to, weight));
                }
            }
            if (scanner.hasNextLine()) // <-- ADDED THIS
                scanner.nextLine();
        }
    } catch (FileNotFoundException | NumberFormatException e) {
    }
    return list.toArray(new Graph.Edge[0]); // <-- ADDED THIS
}

然后，运行同理申请：

Graph g = new Graph(GRAPH);
g.dijkstra(START);
g.printPath(END);
g.printAllPaths();

我测试了所有这些，还发现你的文件输入算法在文件的最后一行中断，所以我在 scanner.nextLine();

之前添加了 if (scanner.hasNextLine())

使用有向图实现 Dijkstra 算法

Implementing Dijkstra's Algorithm Using Directed Graphs

java

graph

directed-graph

dijkstra

adjacency-list