具有负长度循环的有向图中的最短路径
Shortest path in directed graph with cycles of negative length
是否有一种算法可以在包含负长度循环的有向图中找到最短路径？约束是每个节点只能被访问一次，所以解决方案存在。
我知道 Bellman-Ford 算法，但是当存在负循环时它会失败。同样清楚的是，永远遍历负循环会使问题定义不明确，因此我将路径限制为最多访问每个节点一次。
有这样的算法吗？是否有我可以使用的现成实现？
---编辑---
根据下面的要求，这里是实际应用：
给定包含手写体的输入图像，我可以估计每个像素的笔画方向概率：
然后，我可以把像素点做成一个图形，然后找到笔的路径：
看看 "l" 是怎么漏掉的？如果我可以将相邻的权重设置为负数，最优路径将遍历所有字母。但是负权重会产生负循环。
你说得对，Bellman-Ford 算法在这种情况下失败了。您可以参考this resource. It discusses the problem for an undirected graph and works based on Edmonds' Minimum Weight Perfect Matching Algorithm. In fact, you might be interested in this question的第2节，这与您的非常相似。
当图是有向图时，正如@SaiBot 指出的那样，问题就变成了 NP Hard 问题，并且没有有效的解决方案。
是否有一种算法可以在包含负长度循环的有向图中找到最短路径？约束是每个节点只能被访问一次，所以解决方案存在。
我知道 Bellman-Ford 算法，但是当存在负循环时它会失败。同样清楚的是，永远遍历负循环会使问题定义不明确，因此我将路径限制为最多访问每个节点一次。
有这样的算法吗？是否有我可以使用的现成实现？
---编辑---
根据下面的要求，这里是实际应用：
给定包含手写体的输入图像，我可以估计每个像素的笔画方向概率：
然后，我可以把像素点做成一个图形，然后找到笔的路径：
看看 "l" 是怎么漏掉的？如果我可以将相邻的权重设置为负数，最优路径将遍历所有字母。但是负权重会产生负循环。
你说得对，Bellman-Ford 算法在这种情况下失败了。您可以参考this resource. It discusses the problem for an undirected graph and works based on Edmonds' Minimum Weight Perfect Matching Algorithm. In fact, you might be interested in this question的第2节，这与您的非常相似。
当图是有向图时，正如@SaiBot 指出的那样，问题就变成了 NP Hard 问题，并且没有有效的解决方案。