没有楼的楼长的博客

Dijkstra#

Dijkstra is a single-source shortest path algorithm that uses the greedy approach and breadth-first search. Its time complexity is slightly lower than that of SPFA, making it suitable for use in cases where there are no negative edge weights and the data is not random (to avoid SPFA).

Dijkstra uses a greedy strategy to store the distance from each point to the starting point in a dis array. If a point is not directly connected to the starting point, its distance is considered to be infinity (represented by 0x7fffffff, the maximum value of int). The vertices that have been processed (determined to be the shortest path) are marked in an array.

So how do we process it?

First, we traverse the points directly connected to the starting point and find the point with the smallest distance from the starting point, which we call point A. We mark it as processed. Why is point A considered processed? According to the greedy approach, if point A has the smallest distance from the starting point, then the distance from the starting point to any other point and then to point A will definitely be greater than the distance from the starting point directly to point A (which is why Dijkstra is not suitable for graphs with negative edge weights). Then we traverse all points connected to point A. If the distance from the starting point to point A and then to this point is smaller than the distance from the starting point directly to this point, we update the distance from the starting point to this point. This process is called "relaxation". We continue this process until all vertices have been relaxed.

Let's start with a diagram#

First, we construct a graph like this:

Taking A as the starting point, the dis array is as follows (starting from index 0):

We traverse the dis array and find the point E closest to A, and mark it as processed (in green).

Then we traverse the points connected to E and compare the distance from the starting point to E and then to this point. If it is smaller than the distance from the starting point directly to this point, we update the distance from the starting point to this point. For example, for point B, if the distance from the starting point to E and then to B (15) is smaller than the distance from the starting point directly to B ($$\infty$$), we update the distance to B in the dis array. (The red color indicates that it has been processed but is not certain, it is not marked in the program, it is just for convenience of explanation)

Then we traverse to point F, and we find that the distance from A to B to F (9) is smaller than the distance from A to F (10), so we update the distance from A to F in the dis array.

After traversing all the points connected to E, we traverse the dis array again and find the next point that has not been processed and is closest to A, and repeat the steps for E until all points have been processed.

Mark point F as determined

Traverse the points connected to F and update the distances
There are no points connected to F, so we traverse the dis array to find the next one

Mark point B as determined

Traverse the points connected to B and update the distances
There are no points connected to B, so we traverse the dis array to find the next one

Mark point C as determined

Traverse the points connected to C and update the distances

Find point D, 20+5<∞, update the distance from A to D to 25

There are no points connected to C, so we traverse the dis array to find the next one

Mark point D as determined

All points have been updated, and we have obtained the shortest path lengths from point A to all other points.

This is the method of using Dijkstra to find the shortest path from a single source.

Why can't it be used on graphs with negative edge weights?#

So why can't Dijkstra be used on graphs with negative edge weights? Let's explain with a graph.

Taking A as the starting point, the initial dis array is as follows:

If we follow the steps of Dijkstra, the first step is to determine point C.

However, 5 is not the shortest distance from A to C. The distance from A to B to C is 0, which is obviously smaller than 5. But since we have already determined the distance from A to C, we will not update it, resulting in an incorrect answer.

Dijkstra is really a difficult algorithm to learn

Finally, here is what you've been waiting for

Template#

Adjacency matrix storage (starting from 1):

void dijkstra()
{
    memset(dis,127/3,sizeof(dis));//initialize
    v[1]=1;
    dis[1]=0;
    for(int i=1;i<=n;++i)
    {
        int k=0;
        for(int j=1;j<=n;++j)//find the closest point
            if(!v[j]&&(k==0||dis[j]<dis[k]))
                k=j;
        v[k]=1;//add to the set
        for(int j=1;j<=n;++j)//relaxation
            if(!v[j]&&dis[k]+a[k][j]<dis[j])
                dis[j]=dis[k]+a[k][j];
    }
}

Adjacency list storage (with heap optimization):

using namespace std;
const int maxn=250;
struct edge{
	int to,dis,next;
	//define the structure of the edge
};
edge e[maxn*2]; //linked list of edges
int head[maxn],dis[maxn],cnt;
bool vis[maxn];
int n,a,b;

inline void add_edge(int u,int v,int d){
	cnt++;//add the edge
	e[cnt].dis=d;
	e[cnt].to=v;
	e[cnt].next=head[u];
	head[u]=cnt;//store the previous edge
}

struct node{
	int dis;//structure of the point, dis is the distance from point A to this point
	int pos;
	bool operator <(const node &x)const
	{
		return x.dis<dis;//overload the operator, otherwise c++ cannot compare
	}
};

priority_queue<node> q;

inline void dij(){
	dis[a]=0;
	q.push((node){0,a});
	while(!q.empty()){
		node tmp=q.top();
		q.pop();
		int x=tmp.pos,d=tmp.dis;
		if(vis[x]) continue;
		vis[x]=1;
		for(int i=head[x];i;i=e[i].next){
			int y=e[i].to;
			if(dis[y]>dis[x]+e[i].dis){
				dis[y]=dis[x]+e[i].dis; //relaxation
				if(!vis[y]){
					q.push((node){dis[y],y});//enqueue
				}
			}
		}
	}
}

My code is so ugly