java - 最短路径的 Floyd Warshall 算法

Question

我正在浏览一些旧的竞赛问题，我发现了这个，它看起来很有趣，http://dwite.ca/old/Problem5Jan2006.pdf ，我尝试使用 floyd warshall 算法来获取从任何节点到任何其他节点的最短路径，你们能看到我做错了什么吗？它没有给出竞赛问题页面上列出的所需输出

import java.io.*;
import java.util.*;

public class DistanceBetween {


public static void main(String[] args) throws FileNotFoundException {
    Scanner s = new Scanner(new File("DATA5.txt"));
    int n = Integer.parseInt(s.nextLine());
    int[][] dist = new int[60][60];
    for(int y=0;y<60;++y)for(int x=0;x<60;++x)dist[y][x]=10000000;
    Map<Character, Integer> map = new TreeMap<Character, Integer>();
    for (int i = 0; i < n; ++i) {
        String text[] = s.nextLine().split(" ");
        int c = 0;
        if (!map.containsKey(text[0].charAt(0))) {
            map.put(text[0].charAt(0), c);
            c++;
        }
        if (!map.containsKey(text[0].charAt(1))) {
            map.put(text[0].charAt(1), c);
            c++;
        }
        dist[map.get(text[0].charAt(0))][map.get(text[0].charAt(1))] = Integer.parseInt(text[1]);
    }
    for (int k = 0; k < map.size(); ++k) {
        for (int i = 0; i < map.size(); ++i) {
            for (int j = 0; j < map.size(); ++j) {
                dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
    for (int i = 0; i < 5; ++i) {
        String text = s.nextLine();
        System.out.println(dist[map.get(text.charAt(0))][map.get(text.charAt(1))]);
    }
}}

Answer 1

您的代码中存在几个问题:

覆盖映射

您的 int c 是 for 循环的局部变量，这意味着最高使用的映射索引不会保留到下一次迭代，因此下一次迭代中的读取会覆盖上一个。因此，数据加载后距离矩阵没有正确填充。

解决方案:将 int c = 0; 从 for 循环移出。

单向道路

说明中的道路是双向的，但您仅将它们注册为单向。其结果是城镇之间不存在联系。

解决方案:添加 dist[map.get(text[0].charAt(1))][map.get(text[0].charAt(0))] = Integer.parseInt(text[1]); 就在类似的后面。

<小时/>

除了这些难题之外，我还为您提供了一些提示。你没有遵循它们，但如果你想提高你的编程技能那么你应该考虑它们。

凌乱的代码

你的代码难以阅读，有多个重述的信息，例如索引，求解过程是单一方法等。这样的代码不仅难以阅读，而且极难调试并修复。为了你好，我建议你把它写得更干净。

算法效率

Floyd-Warshall 算法的复杂度为O(n^3)。问题的规模(城镇数量)为 A-M = 13。在这种复杂性下，需要进行 13^3 = 2197 次迭代。我知道，这可能看起来不是很多，但请考虑在给定的时间限制内要解决的任务量。

我建议您使用Dijkstra's algorithm其复杂度为O(|E| + |V|log|V|)。在此任务中，经过一些简化后，最坏的情况是 |E| = (|V|^2)/2，|V|=13。这意味着最终的迭代次数为 5 (|V|^2/2 + |V|log|V|) = 5 (13^2/2 + 13 * log13) ~ 5 * 132 = 660 。如果我没有错并且没有犯任何错误，那么这个数字要少得多，特别是当我们考虑任务总量时。

输入读数

我可能是错的，但我参加了多次编程竞赛和竞赛，并且它从未强制参与者使用文件。输入始终从文件重定向到标准输入。我猜想，这样做的主要原因是安全性，但简化也可能是非常有益的。