Java实现Dijkstra算法读取txt文件后最短路径计算异常排查

你读取文件构建图时重复创建了同名的Vertex实例，没有复用已存在的顶点对象，导致relax操作的修改没有作用到图的节点列表中的真实顶点上：

• 手动构建图时，你全程复用了v0~v4这5个Vertex实例，所有边关联的目标顶点和图节点列表中的顶点是同一个对象，relax操作修改的d、p属性自然会同步生效
• 读取文件构建时，处理每一行的邻接节点你都直接new Vertex(currentLine[i])创建新对象，这个新对象和之前已经加入g.nodes的同名顶点只是name属性相同，内存地址完全不同。边中存储的是这个临时创建的顶点对象，relax时修改的也是临时对象的属性，图节点列表里的对应顶点完全没有被修改，自然得不到正确的最短路径结果。

你需要新增一个顶点名到实例的映射表，所有需要获取Vertex实例的场景都优先从映射表中取，不存在才创建新实例，保证同名顶点始终对应同一个对象。
首先需要新增HashMap的导入：

import java.util.HashMap;

以下是修改后的文件读取逻辑代码：

Scanner scanner = new Scanner(System.in);
System.out.print("Please enter file name: ");
String fileName = scanner.nextLine();

Scanner file = new Scanner(new File(fileName));
String sourceID = file.nextLine();
// 新增顶点映射表，保证同名顶点复用同一个实例
HashMap<String, Vertex> vertexMap = new HashMap<>();
Graph g = new Graph(null);

while (file.hasNext()) {
    String[] currentLine = file.nextLine().split(" |,");
    // 从映射表取当前顶点，不存在则创建后存入映射表
    Vertex vertex = vertexMap.computeIfAbsent(currentLine[0], Vertex::new);
    g.addVertex(vertex);
    // 匹配到源点则设置图的源点属性
    if (vertex.getName().equals(sourceID)) {
        g.source = vertex;
    }
    // 处理邻接顶点和边权重
    for (int i = 1; i < currentLine.length; i++) {
        String destName = currentLine[i];
        int weight = Integer.parseInt(currentLine[++i]);
        // 邻接顶点也从映射表取，保证实例唯一
        Vertex dest = vertexMap.computeIfAbsent(destName, Vertex::new);
        g.addEdge(vertex, dest, weight);
    }
}

你代码里用双优先队列重排堆的逻辑效率较低，不过功能上没有问题，学习阶段可以后续再优化实现。

内容的提问来源于stack exchange，提问作者Sarah Cross