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

emmm 还没写完,要不明天再来看 路与路径 从前我一直有这样一个问题:最短路取负不就变成最长路了吗?为什么最短路有这么多算法,而最长路就 NP-Hard 了呢? 这是因为这里没有严格区分 trail(路或迹,可包含重复节点)和 path(路径,有时称简单路径,不包含重复节点) ...