How to optimize Dijkstra algorithm for a single shortest path between 2 nodes?

Question

Hi,

I was trying to understand this implementation in C of the Dijkstra algorithm and at the same time modify it so that only the shortest path between 2 specific nodes (source and destination) is found.

However, I don't know exactly what do to. The way I see it, there's nothing much to do, I can't seem to change d[] or prev[] cause those arrays aggregate some important data for the shortest path calculation.

The only thing I can think of is stopping the algorithm when the path is found, that is, break the cycle when mini = destination when it's being marked as visited.

Is there anything else I could do to make it better or is that enough?

EDIT:
While I appreciate the suggestions given to me, people still fail to answer exactly what I questioned. All I want to know is how to optimize the algorithm to only search the shortest path between 2 nodes. I'm not interested, for now, in all other general optimizations. What I'm saying is, in an algorithm that finds all shortest paths from a node X to all other nodes, how do I optimize it to only search for a specific path?

P.S: I just noticed that the for loops start at 1 until <=, why can't it start at 0 and go until <?

Answer 1

You could perhaps improve somewhat by maintaining a separate open and closed list (visited and unvisited) it may improve seek times a little.

Currently you search for an unvisited node with the smallest distance to source.

1) You could maintain a separate 'open' list that will get smaller and smaller as you iterate and thus making your search space progressively smaller.

2) If you maintain a 'closed' list (those nodes you visited) you can check the distance against only those nodes. This will progressively increasing your search space but you don't have to check all nodes each iteration. The distance check against nodes that have not been visited yet holds no purpose.

Also: perhaps consider following the graph when picking the next node to evaluate: On the 'closed' list you could seek the smallest distance and then search an 'open' node among it's connections. (if the node turns out to have no open nodes in it's connections you can remove it from the closed list; dead end). You can even use this connectivity to form your open list, this would help with islands also (your code will currently crash if you graph has islands).

You could also pre-build a more efficient connection graph instead of a cross table containing all possible node combinations (eg. a Node struct with a neighbours[] node list). This would remove having to check all nodes for each node in the dist[][] array

Instead of initializing all node distances to infinity you could initialize them to the 'smallest possible optimistic distance' to the target and favor node processing based on that (your possibilities differ here, if the nodes are on a 2D plane you could use bird-distance). See A* descriptions for the heuristic. I once implemented this around a queue, not entirely sure how I would integrate it in this code (without a queue that is).

Answer 2

The biggest improvement you can make over Dijkstra is using A* instead. Of course, this requires that you have a heuristic function.

Answer 3

The implementation in your question uses a adjacent matrix, which leads O(n^2) implementation. Considering that the graphs in the real world are usually sparse, i.e. the number of nodes n is usually very big, however, the number of edges is far less from n^2.

You'd better look at a heap-based dijkstra implementation.

BTW, single pair shortest path cannot be solved faster than shortest path from a specific node.

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