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

Question

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

但是,我不确切知道该做什么.我看到它的方式,没有什么可做的,我似乎无法改变d[]或prev[]导致这些数组聚合一些重要数据用于最短路径计算.

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

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

编辑:
虽然我很欣赏给我的建议,但人们仍未能完全回答我的质疑.我想知道的是如何优化算法以仅搜索2个节点之间的最短路径.到目前为止,我对所有其他一般优化都不感兴趣.我所说的是,在找到从节点X到所有其他节点的所有最短路径的算法中,如何优化它以仅搜索特定路径？

PS:我刚注意到for循环开始1直到<=,为什么它不能开始0直到<？

Answer 1

您的问题中的实现使用相邻矩阵,这导致O(n ^ 2)实现.考虑到现实世界中的图形通常是稀疏的,即节点数n通常非常大,但是边缘的数量远小于n ^ 2.

你最好看一下基于堆的dijkstra实现.

BTW,单对最短路径不能比特定节点的最短路径更快地解决.

#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;
}