问题标签 [dijkstra]

a1我得到了一个非常大的单词数组（我们称之为）（比如dog, fish, run,programming任何东西）。

我可以将任何单词 outa1与任何其他单词组合（例如，您可以组合dogand programminginto dog-programming），然后一次又一次，直到字符串变得非常大。

我还有一个a2字符串数组（我们称之为 ）（例如de, s, x?, umh，它们几乎可以是任何东西）。保证在a2a1 的任何字符串中都没有找不到的字符串。

我正在寻找的是包含所有字符串的最短字符串（就创建该字符串所需的组合数量而言最短，而不是该字符串包含多少字符）a2。如果有多个字符串都具有最小长度，我可以选择任何一个，然后退出程序。

现在，我不认为我可以暴力破解，因为即使数组相对较小，也有几乎无穷无尽的组合单词的选择，但我很想被证明是错误的！

有什么好的方法可以得到最短的字符串，肯定会产生最短的结果，还是我必须使用启发式算法来搜索相当短的字符串？

我尝试从 a1 中挑选一个覆盖 a2 中大多数字符串的字符串，然后从 a2 中删除这些项目，然后重新开始，但它不起作用！它产生了很好的结果，但不是最好的。

我为这个问题做了这个实现： http ://www.spoj.pl/problems/SHOP/

我不知道为什么我的代码没有为测试用例生成正确的答案。如果有人可以帮助我改进代码，请这样做：D

我正在查看我的旧算法笔记并遇到了这个证明。这是我的一个作业，我做对了，但我觉得证明确实缺乏。

问题是prove that the distance values taken from the priority queue in Dijkstra's algorithm is a non-decreasing sequence.

我的证明如下：

反证法。首先，假设我们从 Q 中拉出一个 d 值为“i”的顶点。下一次，我们拉出一个 d 值为 'j' 的顶点。当我们拉出 i 时，我们已经确定了我们的 d 值并计算了从起始顶点 s 到 i 的最短路径。因为我们有正的边权重，所以当我们向路径添加顶点时，我们的 d 值不可能缩小。如果从 Q 中拉出 i 后，我们拉出具有较小 d 值的 j，我们可能没有到 i 的最短路径，因为我们可能能够通过 j 到达 i。但是，我们已经计算了到 i 的最短路径。我们没有检查可能的路径。我们不再有保证的路径。矛盾。

如何改进这个证明？或者更好的是，有不同的方法吗？它似乎很弱:)

编辑：对不起，在这种情况下，我的优先级队列是用最小堆实现的

The deadline for this project is closing in very quickly and I don't have much time to deal with what it's left. So, instead of looking for the best (and probably more complicated/time consuming) algorithms, I'm looking for the easiest algorithms to implement a few operations on a Graph structure.

The operations I'll need to do is as follows:

• List all users in the graph network given a distance X
• List all users in the graph network given a distance X and the type of relation
• Calculate the shortest path between 2 users on the graph network given a type of relation
• Calculate the maximum distance between 2 users on the graph network
• Calculate the most distant connected users on the graph network

A few notes about my Graph implementation:

• The edge node has 2 properties, one is of type char and another int. They represent the type of relation and weight, respectively.
• The Graph is implemented with linked lists, for both the vertices and edges. I mean, each vertex points to the next one and each vertex also points to the head of a different linked list, the edges for that specific vertex.

What I know about what I need to do:

• I don't know if this is the easiest as I said above, but for the shortest path between 2 users, I believe the Dijkstra algorithm is what people seem to recommend pretty often so I think I'm going with that.
  • I've been searching and searching and I'm finding it hard to implement this algorithm, does anyone know of any tutorial or something easy to understand so I can implement this algorithm myself? If possible, with C source code examples, it would help a lot. I see many examples with math notations but that just confuses me even more.
  • Do you think it would help if I "converted" the graph to an adjacency matrix to represent the links weight and relation type? Would it be easier to perform the algorithm on that instead of the linked lists? I could easily implement a function to do that conversion when needed. I'm saying this because I got the feeling it would be easier after reading a couple of pages about the subject, but I could be wrong.
• I don't have any ideas about the other 4 operations, suggestions?

我试图在 Dijkstra 算法的 C 中理解这个实现，同时修改它，以便只找到 2 个特定节点（源和目标）之间的最短路径。

但是，我不知道该怎么做。在我看来，没什么可做的，我似乎无法更改d[]或prev[]导致这些数组聚合一些重要数据以进行最短路径计算。

我唯一能想到的就是在找到路径时停止算法，也就是说，mini = destination当它被标记为已访问时打破循环。

我还能做些什么来让它变得更好，或者这就足够了吗？

编辑：
虽然我很欣赏给我的建议，但人们仍然无法准确回答我的问题。我只想知道如何优化算法以仅搜索2 个节点之间的最短路径。目前，我对所有其他一般优化不感兴趣。我要说的是，在找到从节点 X 到所有其他节点的所有最短路径的算法中，如何优化它以仅搜索特定路径？

PS：我刚刚注意到for循环从1until开始<=，为什么它不能从0until开始<？

我用链表实现了我的图，用于顶点和边，这已成为 Dijkstra 算法的一个问题。正如我在上一个问题中所说，我正在转换使用邻接矩阵的代码来处理我的图形实现。

问题是当我找到最小值时，我得到一个数组索引。如果图形顶点存储在数组中，则该索引将与顶点索引匹配。并且对顶点的访问将是恒定的。

我没有时间更改我的图形实现，但我确实有一个哈希表，由一个唯一编号（但不是从 0 开始，就像 100090000）索引，这是我遇到的问题。每当我需要时，我都会使用模运算符来获得一个介于 0 和顶点总数之间的数字。

当我需要来自数字的数组索引时，这很好用，但是当我需要来自数组索引的数字（以在恒定时间内访问计算出的最小距离顶点）时，就不是那么多了。

我试图搜索如何反转模运算，例如 100090000 mod 18000 = 10000 和 10000 invmod 18000 = 100090000 但找不到方法。

我的下一个替代方法是构建某种参考数组，在上面的示例中，arr[10000] = 100090000。这将解决问题，但需要再循环一次整个图。

我当前的图形实现是否有更好/更简单的解决方案？

我有一个有向的正加权图。每个边缘都有使用成本。我只有 A 钱，我想用 dijkstra 算法计算最短路径，但路线上的边成本总和必须小于或等于 A。

我想用最小的 Dijstra 修改来做到这一点（如果我可以用 Dijkstra 的小修改来做到这一点）。如果可以的话，我必须这样做O(n*log(n))，但我想我可以。

任何人都可以帮助我吗？

我想知道 dijkstra 和 prim 的算法，当他们在多个顶点之间进行选择时会发生什么，并且有多个顶点具有相同的权重。

例如

示例图片 http://img688.imageshack.us/img688/7613/exampleu.jpg

有哪些现实生活中的例子，其中每一个都被使用？

我正在研究 Dijkstra 的算法，我真的需要找到所有可能的最短路径，而不仅仅是一条。我正在使用邻接矩阵并应用了 Dijkstra 算法，我可以找到最短路径。但我需要以最低成本找到所有路径，我的意思是所有可能的解决方案，如果它们存在的话。

对于单个解决方案，这就是我的算法的工作原理：