我的问题如下：
我有一个无向图。每条边都有一个成本（或权重）。其中一个节点标记为 S。我想从 S 开始并至少访问每个节点一次。允许多次访问一个节点。允许沿着一条边多次移动，尽管这会使解决方案更加昂贵——以 3 的成本移动一条边两次将使总路径的成本增加 6。该图有一些“死胡同”节点，所以有时我们必须不止一次地遍历一条边。
什么是执行此操作的快速算法？这是一个众所周知的问题吗？
我在找什么：
相当快——我们在这里讨论的图形的相对大小是 40 - 50 个节点的顺序。所以算法希望不会超过 10 - 15 秒。
合理最优——我不是在寻找绝对最优。任何有趣的启发式方法来指导搜索以使解决方案接近最优就足够了。
我将用python写这个。因此，如果您知道该算法的任何 python 实现，那是最好的。
谢谢你的帮助。
如果你有一个节点 $s$ 并且想要找到到节点 $t$ 的最短路径。
如果图具有非负边权重，Dijkstra 算法将在 $O(|E| + |V|\log |V|)$ 时间内找到最优答案。
但是，如果图包含负边权重，Bellman-Ford 算法将在 $O(|V||E|)$ 时间内找到最优答案，但受限于图不包含负权重循环的约束。
这是为了找到图中任意两个节点$u,v$之间的最短路径。它可以通过Floyd-Warshall 算法在时间 $O(|V|^3) 中求解。$ 与 Bellman-Ford 方法类似，该图不得包含负权重循环。
负权循环约束的原因是最短路径可以不断地走循环并减少其权重（如下所示）。
一种简单的方法是为您的图构建最小生成树并在其上进行（深度优先）遍历，跳过已经访问过的节点。
这被证明不超过最佳 TSP 路径的两倍。你绝对可以用启发式方法做得更好，但它是一个初学者（也很容易实现）。
编辑 3：不，仍在寻找
编辑2：
我们去darksky，我已经很久没有这样做了哈哈
D 的算法找到从您的起始节点和图中的每个其他节点的最短距离。
这是一个看起来可以合理修改以使用您的代码的python实现：
编辑：正如评论中正确指出的那样， A* （在一次迭代中）用于单个路径。因此，不满足您访问每个节点一次的要求。我仍然认为 TSP 比您面临的问题要复杂得多，因为您可以访问节点 > 1 次。
原件：A*
我喜欢在大学里解决这个问题，享受吧！