logo标签列表

所有对最短路径问题的最快实现方式是什么？

calgorithmimplementationdijkstrashortest-path
7
我有一个带权重的图，有30k个节点和160k条边，没有负权重。我想计算所有节点之间的最短路径。我认为我不能假设任何特定的启发式方法来简化问题。
我尝试使用这个Dijkstra C实现 http://compprog.wordpress.com/2007/12/01/one-source-shortest-path-dijkstras-algorithm/，它是用于单个最短路径问题的，对我的30个节点调用函数dijkstras()。正如你所想象的那样，这需要很长时间。目前我没有时间自己编写和调试代码，我必须尽快计算这些路径并将它们存储在数据库中，因此我正在寻找另一个更快的可立即使用的解决方案，你有什么建议吗？
我必须在一台配备8GB RAM的最新MacBook Pro上运行它，并且希望找到一个不超过24小时完成计算的解决方案。
非常感谢！ Eugenio
那你的建议是什么？我尝试了这个代码 http://compprog.wordpress.com/2007/12/01/one-source-shortest-path-dijkstras-algorithm/ ，它需要超过一分钟的时间来计算从一个节点到所有最短路径。而且这需要做30k次，所以不可行。 - Eugenio
你确定使用优化标志编译这段代码而非调试模式吗？ - Louis Ricci
这不是调试模式，但我没有使用任何优化标志，我不确定会有什么缺点。 - Eugenio
@LastCoder 这不是调试模式，但我没有使用任何优化标志，我不确定有什么缺点，你建议使用哪种优化？ - Eugenio
2
请注意，您不必从每个节点到所有其他节点执行Dijkstra算法——一旦您知道从A到B的最短路径，您也就知道了从B返回A的最短路径。您还知道该路径上每个节点到该路径上每个其他节点的最短路径。 - caf
5个回答
13

我查看了你在评论中发布的Dijkstra算法链接，我相信这是你效率低下的根源。在内部Dijkstra循环中，它使用了一种极其不优化的方法来确定下一个要探索的节点（即每一步都线性扫描每个节点）。问题代码位于两个位置。第一个就是这段代码，尝试找到下一个要操作的节点：

mini = -1;
for (i = 1; i <= n; ++i)
    if (!visited[i] && ((mini == -1) || (d[i] < d[mini])))
         mini = i;

由于此代码嵌套在访问每个节点的循环中，所以复杂度（如链接中所述）为O（|V|2），其中 |V| 是节点数。 在您的情况下，由于 |V| 为 30,000，这个循环总共将迭代九亿次。 这非常慢（正如您所见），但是没有理由必须做这么多的工作。

另一个麻烦点在于这里，它试图找到应使用哪个图中的边来减少其他节点的成本：

for (i = 1; i <= n; ++i)
   if (dist[mini][i])
       if (d[mini] + dist[mini][i] < d[i])
           d[i] = d[mini] + dist[mini][i];
这段代码扫描整个邻接矩阵中的一行，查找要考虑的节点，这需要时间O(n)，无论一个节点有多少出边。
虽然你可以尝试将此版本的Dijkstra算法改进为更优化的实现方式，但我认为在这里正确的选项是放弃这段代码，寻找更好的Dijkstra算法实现。例如，如果使用从维基百科文章伪代码实现的二叉堆，则可以使Dijkstra算法运行时间为O(|E| log |V|)。在您的情况下，该值仅略高于两百万，比当前方法快约450倍。这是一个巨大的差异，我相信通过更好的Dijkstra算法实现，您最终会使代码完成时间显著缩短。
此外，您可能还希望考虑并行运行所有Dijkstra搜索，正如Jacob Eggers所指出的那样。这对于每个处理器都可以为您提供额外的速度提升。结合上述（也更为关键）的修复措施，这应该能够极大地提高性能。
如果您计划在更密集的数据集上运行此算法（其中边的数量接近于|V|2 / log |V|），则可能要考虑切换到Floyd-Warshall算法。对每个节点运行Dijkstra算法一次（有时称为Johnson算法）需要时间O(|V||E| log |V|)，而使用Floyd-Warshall算法需要时间O(|V|3)。但是，对于您提到的数据集来说，图足够稀疏，运行多个Dijkstra实例应该没有问题。
希望这能帮助到您！
这是一个非常全面的答案！A+。 - j_random_hacker
@templatetypedef 感谢您的好分析！我尝试使用这个代码 http://www.cs.rochester.edu/~nelson/courses/csc_173/graphs/apsp.html 切换到floyd算法，显然时间复杂度为O(|V|3)，但仍然非常非常慢...一个节点需要3-4分钟（您觉得这个计时有意义吗？），这意味着需要3分钟*30k来计算所有路径。正如我之前所写，由于没有太多时间，所以我正在尝试避免从头开始重写和调试一个实现。我真的很惊讶在网上没有找到任何高质量的C语言Dijkstra算法的实现！ - Eugenio
这完全是一个不要脸的自我推销，但是我之前写了一个使用斐波那契堆实现Dijkstra算法的程序（运行时间为O（E + V log V），非常快）。代码已经在我的个人网站上（Java语言）发布：http://keithschwarz.com/interesting/code/?dir=dijkstra - templatetypedef
2
@Eugenio- 正如我在答案中提到的，我强烈建议不要在这里使用 Floyd-Warshall 算法，因为它比反复调用 Dijkstra 算法要低效得多。如果你时间紧迫，最好花几个小时找到/编写一个好的 Dijkstra 算法并使用它，因为你投入的时间来减少执行时间将使得获得结果成为可能，而不是使用一个慢速版本，这将无法给你任何东西。 - templatetypedef
@templatetypedef 再次感谢您；我尝试优化cs.rochester.edu/~nelson/courses/csc_173/graphs/apsp.html。实际上，代码不需要3个30kx30k的矩阵，只需要两个（您可以只使用矩阵D和P，对吧？）。在进行这些更改并设置-O gcc标志后，代码现在每个节点所需的时间少于2秒，这意味着我可以在半天内运行所有内容。 此外，实际上，在我的图中，a->b的权重始终与b->a相同，我能利用这一点吗，还是应该考虑它？ - Eugenio
@templatetypedef 再次感谢，我试图优化cs.rochester.edu/~nelson/courses/csc_173/graphs/apsp.html实际上代码不需要3个30kx30k的矩阵，只需要两个（您可以只使用矩阵D和P，对吧？）。在这个更改和-O gcc标志设置后，现在每个节点的代码只需要少于2秒，这意味着我可以在半天内运行所有内容。此外，在我的图形中，a->b的权重总是与b->a相同，我可以利用它还是应该考虑它？ - Eugenio
4
2
由于边数与节点数的比例较低，Floyd-Warshall算法往往比多次运行Dijkstra算法来得慢。FW算法的复杂度为O(V^3)，而多个Dijkstra调用需要O(VE+V^2 log V)。如果E=O(V)，则可以降至O(V^2 log V)。由于OP的输入相当大，我希望多次运行Dijkstra算法会更快地运行。 - templatetypedef
2

你的图形有特殊结构吗？这个图是平面的（或者近似平面）吗？

我建议不要尝试存储所有的最短路径，一个相当密集的编码（30k ^ 2 "下一步去哪" 条目）将占用7G内存。

应用程序是什么？当你需要找到特定的最短路径时，你确定做双向Dijkstra（如果你有一个启发式）不够快吗？

我认为它不是平面的或具有其他特殊结构，你为什么说是7G？它有900M个条目对吧？该应用程序是基于Web的，并且需要立即得到答案，因此我想将路径存储在数据库中，你认为请求特定路径是否可以在不到两秒钟内完成？@rrenaud - Eugenio
我认为每个条目的成本将是8字节。但实际上，如果你有30k，log（30k）〜15，因此你可以使用每个条目2字节。 - Rob Neuhaus
0

瓶颈可能是您用于存储路径的数据结构。如果使用太多存储空间，很快就会耗尽缓存和内存空间，导致快速算法运行非常缓慢，因为它获得了100（缓存未命中）或10000+（交换页面）常数乘数的顺序。

因为您必须在数据库中存储路径，我怀疑这可能很容易成为瓶颈。最好先将路径生成到内存中，使用非常高效的存储模式，例如每个顶点N位，其中N ==每个顶点的最大边数。然后为可以用于生成最短路径之一的每条边设置一个位。生成此路径信息后，您可以运行递归算法，将路径信息生成适合数据库存储的格式。

当然，最有可能的瓶颈仍然是数据库。您需要非常仔细地考虑使用何种格式存储信息，因为在SQL数据库中插入、搜索和修改大型数据集非常缓慢。此外，使用事务执行数据库操作可能能够减少磁盘写入开销，如果数据库引擎成功将多个插入路径合并为单个磁盘写入操作。

将结果简单地存储在内存缓存中，并在不再需要时丢弃解决方案，这样可能会更好。如果您再次需要它们，则再次生成相同的结果。这意味着只有在实际需要它们时才会按需生成路径。对于30k个节点和160k条边的运行时间，Dijkstra的单个最短路径运行时间应明显低于一秒。

对于最短路径算法，我总是选择C ++。虽然C实现也应该很简单，但C ++提供了使用STL容器进行初始实现并仅在基准测试和分析表明需要比STL提供的更好的优化队列算法时才实现的减少编码的方法。

#include <queue>
#include "vertex.h"

class vertex;
class edge;

class searchnode {
    vertex *dst;
    unsigned long dist;
    public:
    searchnode(vertex *destination, unsigned long distance) :
        dst(dst),
        dist(distance)
    {
    }

    bool operator<(const searchnode &b) const {
        /* std::priority_queue stores largest value at top */
        return dist > b.dist;
    }

    vertex *dst() const { return dst; }

    unsigned long travelDistance() const { return dist; }
};


static void dijkstra(vertex *src, vertex *dst)
{
    std::priority_queue<searchnode> queue;

    searchnode start(src, 0);
    queue.push(start);

    while (!queue.empty()) {
        searchnode cur = queue.top();
        queue.pop();

        if (cur.travelDistance() >= cur.dst()->distance())
            continue;

        cur.dst()->setDistance(cur.travelDistance());
        edge *eiter;
        for (eiter = cur.dst()->begin(); eiter != cur.dst()->end(); eiter++) {
            unsigned nextDist = cur.dist() + eiter->cost();

            if (nextDist >= eiter->otherVertex())
                continue;

            either->otherVertex()->setDistance(nextdist + 1);

            searchnode toadd(eiter->othervertex(), nextDist);
            queue.push(toadd);
        }
    }
}
0

如果您可以将算法修改为多线程，您可能能够在不到24小时的时间内完成它。

第一个节点可能需要超过1分钟的时间。然而，第15,000个节点应该只需要一半的时间，因为您已经计算出了所有先前节点的最短路径。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接