带负权边的无向图上的最短路径问题

有趣的问题
路与路径 从前我一直有这样一个问题：最短路取负不就变成最长路了吗？为什么最短路有这么多算法，而最长路就 NP-Hard 了呢？ 这是因为这里没有严格区分 trail（路或迹，可包含重复节点）和 path（路径，有时称简单路径，不包含重复节点）。 我们平常所说的最短路问题是希望计 ...
Read More
problem solving 图论