Note excerpts
Crap:
I have to marvel at the power of chain forward stars. Yesterday I learned how to sort the topology and understand the magic usage of head [] and next. I didn't expect that I could not build a map when I wrote a topic today. I learned spfa(), which I thought was useless until now. I learned a lot!!!
SPFA algorithm in detail (shortest path)
Advantages of the algorithm:
1: Time complexity is lower than ordinary Dijkstra and ford
2: Ability to compute negative weight graphs
3: Can judge whether there is a negative ring (i.e. every lap, the path will be reduced, so it will continue to run in circles)
Algorithmic ideas:
We use arrays to record the shortest path estimates for each node, and adjacency tables to store graph G.
The method we adopt is dynamic approximation method.
1: Set up a first-in-first-out queue to save the nodes to be optimized.
2: When optimizing, the first node u is taken out each time, and the current shortest path estimation of u is used to relax the point v pointed to leave u. If the shortest path estimation of V is adjusted and V is not in the current queue, the V-point is put into the end of the queue.
3: In this way, the nodes are removed from the queue to relax until the queue is empty.
Expected time complexity O(ke), where k is the average number of entries at all vertices, can prove that K is generally less than or equal to 2.
Method of realization:
1: Save in the graph. You can use chain forward stars or vector s
2: Open a queue, first put the starting node in
3: Take an X out of the queue each time, traverse the Y node connected with x, and query the length of Y and the length of X + the length of X and Y.
If the length of X + the length of X over Y is longer than the length of Y, the update operation is required.
(1) Shortest path to deposit
(2) Because the original length has been changed, it needs to be updated later, and the shortest path connected to this node. (Judging whether or not in the queue, you don't have to repeat, you don't join the queue and wait for updates)
(3) During this period, the number of queues of this node can be recorded to determine whether there is a negative ring or not.
4 until the queue is empty
Judging whether there is a negative ring: If a point enters the queue more than N times, there is a negative ring.
Chain forward star + spfa() realizes the shortest path:
explain
According to the chain forward star mapping method (which involves next and head []), we can record that each point points to several points.
Now that we know how many points each point points points to, we can use our greedy algorithm to solve the problem.
If the weight of 1 - > 2 is 2, 1 - > 3 is 3, we can get the shortest distance by comparing the distances of several points connected by 1 - > and then press unused points into the queue. According to the greedy algorithm, we can quickly find the shortest distance from a single source point to the point he wants.
Examples:
Title:
Solution 1: Realization of ordinary Dijstra
AC code:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
//Adjacency table mapping
//Dijkstra
#define maxn 2005
#define inf 0x3f3f3f3f
int Map[maxn][maxn];//Save map
int dis[maxn];//distance
int book[maxn];//Marking
int n;//Number of points
void Dijkstra(int u)//Single source shortest path
{
memset(book,0,sizeof(book));//Clean up arrays
for(int i=1;i<=n;i++)
dis[i]=inf;//Let all points be inaccessible and assign inf
dis[u]=0;//Making single source point achievable
int minx,pos;//Duel out the minimum point
for(int i=1;i<=n;i++)
{
minx=inf;
for(int j=1;j<=n;j++)
{
if(!book[j]&&dis[j]<minx)
{
minx=dis[j];
pos=j;
}
}
book[pos]=1;//It will not be used next time after marking.
for(int k=1;k<=n;k++)
{
if(!book[k]&&dis[k]>dis[pos]+Map[pos][k])
{
dis[k]=dis[pos]+Map[pos][k];
}
}
}
}
int main()
{
int m;
while(~scanf("%d %d",&m,&n))
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
Map[i][j]=inf;
Map[i][i]=0;
}
int u,v,val;
while(m--)
{
scanf("%d %d %d",&u,&v,&val);
Map[u][v]=Map[v][u]=min(val,Map[u][v]);
}
//int st;
//scanf("%d",&st);
Dijkstra(1);//Shortest path from single source to other locations
//int en;
//scanf("%d",&en);
printf("%d\n",dis[n]);
}
}
Scheme 2: Chain Forward Star
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
//Chain forward star optimization spfa
#define maxn 10005
struct node
{
//int from;//starting point
int to;//End
int val;//Weight
int next;//addressing
}graph[maxn];
int book[maxn];
int head[maxn];
int dis[maxn];
//int book[maxn];
int n,m,cnt;
void input(int u,int v,int w)//input
{
graph[cnt].to=v;
graph[cnt].val=w;
graph[cnt].next=head[u];//Addressing operation
head[u]=cnt++;
}
void spfa(int s)
{
memset(dis,0x3f3f3f3f,sizeof(dis));
memset(book,0,sizeof(book));
dis[s]=0;
queue<int>q;
q.push(s);//Put s in pairs
while(!q.empty())
{
int st=q.front();
q.pop();
book[st]=0;
for(int k=head[st];k!=-1;k=graph[k].next)//Recorded points pointed to by a single source point
{
int v=graph[k].to;//The point where st goes
int w=graph[k].val;//The Weight of the Point to which st goes
if(dis[v]>dis[st]+w)
{
dis[v]=dis[st]+w;
if(book[v]==0)
{
book[v]=1;
q.push(v);
}
}
}
}
}
int main()
{
while(~scanf("%d %d",&m,&n))
{
cnt=0;
memset(head,-1,sizeof(head));
int u,v,w;
while(m--)
{
scanf("%d %d %d",&u,&v,&w);
input(u,v,w);
input(v,u,w);
}
//int s,en;
//scanf("%d",&s);
spfa(1);
//scanf("%d",&en);
printf("%d\n",dis[n]);
}
}