问题标签 [shortest]

在具有负和正权重的有向图中使用下面的 SPFA 算法，我们如何检测负循环？

procedure Shortest-Path-Faster-Algorithm(G, s)

我试图根据长度找到最短和最长的字符串值，但我被卡住了。到目前为止，脚本在写入行之后退出。我认为代码需要一些帮助，我认为 for 循环不能单独工作。任何援助将不胜感激。

我正在使用graphstream库在java中递归地构建一个图。但是这个图非常大，以至于递归非常深，这以stackoverflow结束。相信我，即使是迭代也不能解决我的问题。我只会在路上遇到运行时错误。

我的目标是最终在图表上使用诸如 Disjktra 或 A* 之类的搜索算法。

由于我没有完整的图表，我一直在文献中寻找诸如局部地图中的最短路径算法之类的东西；使用启发式我找不到太多。

如果有人能给我一些提示，我将不胜感激（论文，想法；实现将是一个大奖！！！：-D）我已经研究过诸如 PHA* 或其他一些算法。

我对基于优先级的抢先式最短作业优先算法有疑问。如果两个进程具有相同的优先级，那么谁是第一个。是先放入的还是突发时间较短的？如果我有 2 个具有相同突发时间的进程，突发时间也是如此，我是否按优先级排序？如果两个进程具有相同的突发时间和优先级会发生什么？

例如，基于此表的甘特图会是什么样子？

任何人都可以在上面具有负权重的无向图中应用 Dijkstra 算法吗？即使算法失败。

邻接名单：

我正在尝试实现来自Chess Programming Wiki的Knight-Distance中描述的绝对等级文件距离，但我对s和应该在什么中有点困惑intab

你不需要两组坐标来计算这个（开始位置和目的地）吗？我想也许他们使用 0,0 作为开始，然后你只给出开始和结束位置之间的差异，但这会产生糟糕的输出。

这应该如何工作，这个算法是否适用于任何尺寸的网格，或者只是 8×8？

我有一组 N 点，我有坐标（军械测量网格参考）。我想从 A 点开始，在 B 点结束，并以最少的旅行时间访问沿途的所有其他点。

我已经获得了 Mathematica 9，但我正在努力解决它。我尝试了 FindShortestTour，但它想让我回到起点。有什么建议么？

我的问题如下。

我有一个“备份”节点和其他节点。从这些节点，我需要生成一个到备份节点的公共路径，该路径是最小的（未加权和无向图）我不需要每次都需要解决方案。我怎么知道我是否可以生成这条路径。

我正在考虑将图拆分为一些子图并搜索最小的“子路径”。

但是我在图论方面不是很好。我使用 Python 和 C++。

提前谢谢你。

（对不起，如果已经有这样的问题，我已经搜索过了，但没有找到）

给定一组具有经度和纬度的 Y 点（位置），穿过一组唯一 X 点的最短路径是什么？

只是我在设计数据库时遇到的算法问题。不知道如何继续，或者是否有一个优雅的解决方案来解决这个问题。请帮忙！谢谢！

编辑：这不是旅行推销员问题，它不是访问所有位置的最短路径，而是任何穿过 X 点的唯一集合。

例如，如果我们有 2000 个位置，那么访问任意 10 个位置的最短路径是多少？

与整个 Y 集合相比，X 的大小将非常小。

所以我一直在尝试使用邻接列表在有向图中实现最短路径的 Dijkstra 算法，但由于我不知道是什么原因，它不会打印出结果（将最小距离打印为 0 到所有节点） .

我写的代码是：

输入数据是：

这意味着有 5 个节点，7 条弧（有向边），弧从节点 1 到 2，成本为 10，从 1 到 3，成本为 2，依此类推。

但是，输出是错误的。我不知道程序可能在哪里失败。我从这里得到了主要思想：http: //community.topcoder.com/tc ?module=Static&d1=tutorials&d2=standardTemplateLibrary2# dijkstra1（最后它给出了使用priority_queue的Dijkstra算法的想法）。

提前致谢。

劳尔