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

Question

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

但是，我不知道该怎么做。我看到它的方式，没有什么可以做的，我似乎无法改变d[]或prev[]导致这些数组汇总最短路径计算的一些重要数据。

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

还有什么我可以做得更好或足够吗？

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

P.S：我刚刚注意到for循环在1开始直到<=，为什么就不能启动在0和去，直到<？

Answer 1

在你的问题中的实现使用了一个相邻的矩阵，它导致了O（n^2）的实现。考虑到现实世界中的图通常是稀疏的，即节点数n通常非常大，但是，边的数量远小于n^2。

你最好看看heap-based dijkstra implementation。

顺便说一句，单对最短路径不能快于来自特定节点的最短路径。

#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）如果你维护一个'封闭'列表（你访问过的那些节点），你可以只检查那些节点的距离。这将逐渐增加您的搜索空间，但您不必每次迭代都检查所有节点。对尚未访问过的节点进行距离检查并没有目的。

另外：或许可以考虑在选择下一个节点进行评估时遵循图：在“封闭”列表中，您可以寻找最小距离，然后在其连接中搜索“开放”节点。 （如果该节点的连接中没有开放节点，则可以将其从关闭列表中移除;死胡同）。 你甚至可以使用这种连接来形成你的开放列表，这也将有助于岛屿（如果你的图形有孤岛，你的代码将会崩溃）。你也可以预先构建一个更高效的连接图，而不是一个包含所有可能的节点组合的交叉表（例如，一个具有neighbors []节点列表的节点结构）。这将消除必须检查dist [] []数组中每个节点的所有节点

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

Answer 3

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