如何针对两个节点之间的单个最短路径优化 Dijkstra 算法？

Question

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

但是，我不知道到底要做什么。在我看来，没有什么可做的，我似乎无法更改 d[] 或 prev[] 因为这些数组在最短的时间内聚合了一些重要数据路径计算。

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

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

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

PS：我刚刚注意到for循环从1开始直到<=，为什么不能从0<开始/code> 直到 <?

Answer 1

您问题中的实现使用相邻矩阵，这导致 O(n^2) 实现。考虑到现实世界中的图通常是稀疏的，即节点数n通常很大，但边的数量却远远少于n^2。

您最好查看基于堆的 dijkstra 实现。

顺便说一句，单对最短路径的求解速度不能比特定节点的最短路径更快。

#include<algorithm>
using namespace std;

#define MAXN 100
#define HEAP_SIZE 100
typedef int Graph[MAXN][MAXN];

template <class COST_TYPE>
class Heap
{
public:
    int data[HEAP_SIZE],index[HEAP_SIZE],size;
    COST_TYPE cost[HEAP_SIZE];
    void shift_up(int i)
    {
        int j;
        while(i>0)
        {
            j=(i-1)/2;
            if(cost[data[i]]<cost[data[j]])
            {
                swap(index[data[i]],index[data[j]]);
                swap(data[i],data[j]);
                i=j;
            }
            else break;
        }
    }
    void shift_down(int i)
    {
        int j,k;
        while(2*i+1<size)
        {
            j=2*i+1;
            k=j+1;
            if(k<size&&cost[data[k]]<cost[data[j]]&&cost[data[k]]<cost[data[i]])
            {
                swap(index[data[k]],index[data[i]]);
                swap(data[k],data[i]);
                i=k;
            }
            else if(cost[data[j]]<cost[data[i]])
            {
                swap(index[data[j]],index[data[i]]);
                swap(data[j],data[i]);
                i=j;
            }
            else break;
        }
    }
    void init()
    {
        size=0;
        memset(index,-1,sizeof(index));
        memset(cost,-1,sizeof(cost));
    }
    bool empty()
    {
        return(size==0);
    }
    int pop()
    {
        int res=data[0];
        data[0]=data[size-1];
        index[data[0]]=0;
        size--;
        shift_down(0);
        return res;
    }
    int top()
    {
        return data[0];
    }
    void push(int x,COST_TYPE c)
    {
        if(index[x]==-1)
        {
            cost[x]=c;
            data[size]=x;
            index[x]=size;
            size++;
            shift_up(index[x]);
        }
        else
        {
            if(c<cost[x])
            {
                cost[x]=c;
                shift_up(index[x]);
                shift_down(index[x]);
            }
        }
    }
};



int Dijkstra(Graph G,int n,int s,int t)
{
    Heap<int> heap;
    heap.init();
    heap.push(s,0);
    while(!heap.empty())
    {
        int u=heap.pop();
        if(u==t)
            return heap.cost[t];
        for(int i=0;i<n;i++)
            if(G[u][i]>=0)
                heap.push(i,heap.cost[u]+G[u][i]);
    }
    return -1;
}

Answer 2

您也许可以通过维护一个单独的打开和关闭列表（已访问和未访问）来有所改进，它可能会稍微缩短查找时间。

当前，您搜索与源距离最小的未访问节点。

1）您可以维护一个单独的“开放”列表，随着您的迭代，该列表会变得越来越小，从而使您的搜索空间逐渐变小。

2）如果您维护一个“封闭”列表（您访问过的那些节点），您可以仅检查这些节点的距离。这将逐渐增加您的搜索空间，但您不必每次迭代都检查所有节点。对尚未访问过的节点进行距离检查没有任何意义。

另外：在选择要评估的下一个节点时，也许可以考虑遵循图表：在“闭合”列表上，您可以寻找最小距离，然后在其连接中搜索“开放”节点。 （如果该节点的连接中没有开放节点，您可以将其从关闭列表中删除；死胡同）。
您甚至可以使用此连接来形成打开列表，这也有助于处理岛屿（如果您的图形有岛屿，您的代码当前将崩溃）。

您还可以预先构建一个更有效的连接图，而不是包含所有可能的节点组合的交叉表（例如，带有 neighbours[] 节点列表的 Node 结构）。这将消除检查 dist[][] 数组中每个节点的所有节点的麻烦，

而不是将所有节点距离初始化为无穷大，您可以将它们初始化为到目标的“最小可能乐观距离”，并基于该距离有利于节点处理（这里你的可能性有所不同，如果节点位于 2D 平面上，你可以使用鸟类距离）。有关启发式，请参阅 A* 描述。我曾经围绕队列实现过这个，但不完全确定如何将它集成到这段代码中（没有队列）。

Answer 3

您可以对 Dijkstra 进行的最大改进是使用 A* 代替。当然，这需要你有启发式功能。