Detailed decomposition of the shortest path problem in Figure

High quality resource sharing

Learning route guidance （ Click unlock ）	Knowledge orientation	Crowd positioning
🧡 Python Actual wechat ordering applet 🧡	Progressive class	This course is python flask+ Perfect combination of wechat applet , From the deployment of Tencent to the launch of the project , Create a full stack ordering system .
Python Quantitative trading practice	beginner	Take you hand in hand to create an easy to expand 、 More secure 、 More efficient quantitative trading system

The shortest path problem of graphs Detailed breakdown

1. Classification of shortest path problem in graph

2. Single source shortest path problem

2.1 When the edge weights are all positive

2.1.1 simple Dijstra Algorithm

Algorithmic thought ： Each time, find the node with the minimum distance from the starting point from the node that has never been determined as the shortest distance , Join the collection s in , And use this node to update the path of other nodes whose shortest path value has not been determined . Until the shortest path value of all nodes is finally calculated , This collection s Set for all nodes .

#include
using namespace std;

const int N = 510;
int g[N][N];// A dense picture , Adjacency matrix storage 
int st[N];// Have you ever been interviewed , I.e. whether the s Collection 
int dist[N];// Record the distance from each point to the starting point 
int n,m;
// Return No n Node to 1 The shortest path of node No 
int dijstra(){
    memset(dist,0x3f,sizeof dist);// Initialize the distance to infinity 
    dist[1]=0;//1 The distance of node No. is initialized to 0
    for(int i=0;i//n Wheel cycle , Find one node at a time , Join in s aggregate , And use it to update other nodes dist Array . There has to be n Wheel cycle , Because to update dist Array 
 int t=-1;
 for(int j=1;j<=n;j++){// Loop to find the starting point of the current distance 1 Node No. is closest , And did not join s The node of 
 if(!st[j]&&(t==-1||dist[j]true;// Add this node to s Array 
 for(int j=1;j<=n;j++){// Update the distance of other nodes circularly 
 if(!st[j]){
 dist[j]=min(dist[j],dist[t]+g[t][j]);
 }
 }
 }
 if(dist[n]==0x3f3f3f3f) return -1;// If dist[n] Not updated , Explain that it is not reachable 
 return dist[n];
}

int main(){
 memset(g,0x3f,sizeof g);// The distance between initialization nodes is infinite 
 cin>>n>>m;// The input data contains n Nodes ,m side 
 int a,b,c;
 while(m--){
 cin>>a>>b>>c;// Input m side , The input data has self ring and double edge , Take the minimum value 
 g[a][b]=min(g[a][b],c);
 }
 cout<<dijstra()<return 0;
}

Algorithm analysis ： The algorithm consists of two cycles , The time complexity is O(n2)O(n2)O(n^2)

2.1.2 Heap optimized Dijstra Algorithm

Optimize ideas ： simple Dijstra Each time, the algorithm must find the node closest to the starting point , Join the collection s in . We can use the heap to maintain the distance between the node and the starting point , One cycle is omitted .

// Sparse graph dijstra
#include
using namespace std;

const int N = 1.5e5+10;

int e[N],ne[N],w[N],h[N],idx;// Sparse graph , Using adjacency list to store 

int n,m;//n Nodes ,m side 

int dist[N];// Distance array 
bool st[N];// Have you ever visited , namely s Assembly marks 

typedef pair<int, int> PII;// Use heap auto sort ,pair Of first For distance ,second Is number 

void add(int a,int b,int c){// Add node a->b The edge of , A weight of c
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}

int dijstra(){
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    priority_queue,greater> q;// Declare the small root heap 
 q.push({0,1});//1 Node number joins the queue 
 while(!q.empty()){
 PII t=q.top();
 q.pop();
 int distance=t.first,x=t.second;
 if(st[x]) continue;// The distance has been determined , skip 
 st[x]=true;
 for(int i=h[x];i!=-1;i=ne[i]){
 int j=e[i];
 if(dist[x]+w[i]push({dist[j],j});
 }
 }
 }
 if(dist[n]==0x3f3f3f3f) return -1;
 return dist[n];
}

int main(){
 cin>>n>>m;
 int a,b,c;
 memset(h,-1,sizeof h);
 while(m--){
 cin>>a>>b>>c;
 add(a,b,c);
 }
 cout<<dijstra()<return 0;
}

Algorithm analysis ：
Time complexity ： Each time you find the point with the minimum distance, update other points along the edge , if dist[j] > distance + w[i], Indicates that it can be updated dist[j], Update and then j Put the point and the corresponding distance into the small root pile . Because the number of points is n, The number of sides is m, In extreme cases （ A dense picture m=n∗n(n−1)2m=n∗n(n−1)2m=\frac{n*n(n-1)}{2}） Up to... Can be updated m return , Up to... Can be updated each time n2n2n^2 A little bit （ Strictly speaking n - 1 A little bit ）, Yes m return , So at most n2n2n^{2 Put a point into the small root pile , So every time the small root heap sort is updated O(log(n2))O(log(n2))O(log(n}2)), At most m Secondary update , Therefore, the upper limit of the total time complexity is O(mlog((n2)))=O(2mlogn)=O(mlogn)O(mlog((n2)))=O(2mlogn)=O(mlogn)O(mlog((n^2)))=O(2mlogn)=O(mlogn)
doubt ： Why is there a distance that has been determined by the point in the heap ？
Because it may have been added to the collection last time s The element of has been updated a The distance value of , But the distance is very big , until a The distance value of is determined pop come out .

2.2 When the edge weights are negative

2.2.1 Bellman-ford Algorithm

Algorithmic thought ： If there is n A little bit , So after n-1 Secondary cycle , Relax each edge in each cycle , If in n-1 It can be renewed after relaxation , Then it shows that there is a negative ring in the figure , Therefore, no results can be obtained , Otherwise, complete .
Slack operation ：

for n Time 
	for  All sides  a,b,w ( Slack operation )
		dist[b] = min(dist[b],back[a] + w)

Be careful ：back[] The array is after the last iteration dist[] Backup of array , Because every point starts out at the same time , So you need to dist[] Array for backup , If you don't do a backup, there will be a cascading effect , To the next point .

In the following code , Whether we can reach n In the judgment of No if(dist[n] > INF/2) Judge , It is not. if(dist[n] == INF) Judge , as a result of INF It's a definite value , It's not really infinity , Will be affected by other values ,dist[n] Greater than one with INF The same order of magnitude .

bellman - ford The algorithm is good at solving the shortest path problem with limited number of edges .

// This code is to solve the shortest path problem with the number of edges 
#include
using namespace std;

const int N = 10010;
int n,m,k;
int dist[510],backup[510];

struct{
    int a,b,w;
}edges[N];//a->b There is one side , The weight of w

int bellman\_ford(){
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    for(int i=0;i// most k side , Total most correct process k side 
 memcpy(backup,dist,sizeof dist);
 for(int j=0;j// For all the m The edge is relaxed 
 int a=edges[j].a,b=edges[j].b,w=edges[j].w;
 if(backup[a]+wif(dist[n]>0x3f3f3f3f/2) return -0x3f3f3f3f;
 else return dist[n];
}

int main(){
 cin>>n>>m>>k;
 int a,b,w;
 for(int i=0;i>a>>b>>w;
 edges[i]={a,b,w};
 }
 int ans=bellman\_ford();
 if(ans==-0x3f3f3f3f){
 cout<<"impossible"<else{
 cout<return 0;
}

Algorithm analysis ：
Time complexity ：O(nm)O(nm)O(nm), among n For points ,m Number of sides

2.2.2 SPFA Algorithm

Algorithmic thought ： To optimize the Bellman-ford Algorithm . stay Bellman-ford In the algorithm, ,dist[b] = min(dist[b],back[a] + w), If a The distance has not been updated , So my loop actually does a lot of useless operations . So we want to be a When the distance is updated , Use it again a Update the distance value of other nodes . The algorithm idea is similar to Dijstra Algorithm .

#include
using namespace std;

const int N = 1e5+10;

int e[N],w[N],h[N],ne[N],idx;

int n,m;

int st[N];// Record whether the node is in the queue , That is, whether an update has occurred 
int dist[N];

void add(int a,int b,int c){
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}

int spfa(){
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    queue<int> q;
    q.push(1);
    while(!q.empty()){
        int t=q.front();
        q.pop();
        st[t]=false;
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(dist[j]>dist[t]+w[i]){// Slack operation 
                dist[j]=dist[t]+w[i];
                if(!st[j]){// Node distance update occurs , So you can use this node to update other nodes 
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
    if(dist[n]==0x3f3f3f3f) return -0x3f3f3f3f;
    return dist[n];
}

int main(){
    memset(h,-1,sizeof h);
    cin>>n>>m;
    int a,b,c;
    while(m--){
        cin>>a>>b>>c;
        add(a,b,c);
    }
    int ans=spfa();
    if(ans==-0x3f3f3f3f) cout<<"impossible"<else cout<return 0;
}

Algorithm analysis ：
Bellman_ford At the end of the algorithm return -1 The judgment condition of is dist[n]>0x3f3f3f3f/2; and spfa The algorithm is written dist[n]==0x3f3f3f3f; And the reason is that Bellman_ford The algorithm will traverse all the edges , Therefore, whether it is an edge connected to the source point or not, it will be updated ; however SPFA The algorithm is different , It is equivalent to using BFS, Therefore, all nodes traversed are connected with the source point , So if you ask n Disconnected from the source , It won't be updated , Still keep it 0x3f3f3f3f.

Bellman_ford The algorithm can have a negative weight loop , Because the number of cycles is limited, there will be no life and death cycle in the end ; however SPFA The algorithm cannot , Because queues are used to store , As long as there are updates, they will continue to join the team , Therefore, if there is a negative weight circuit, please don't use SPFA Otherwise, there will be a dead cycle .

because SPFA The algorithm is based on Bellman_ford Algorithm optimization , In the worst case, the time complexity is the same as it, that is, the time complexity is O(nm)O(nm)O(nm) , If time permits, you can directly use SPFA Algorithm to solve Dijkstra The problem of algorithm .

Finding a negative ring generally uses SPFA Algorithm , The method is to use a cnt The array records the number of sides from each point to the source point , A point is updated once +1, Once the number of sides of a point reaches n That proves the existence of a negative ring .

3. Multi source sink shortest path problem

Floyd Algorithm

Algorithmic thought ： Triple cycle , Dynamic planning ideas .dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])

#include
using namespace std;

const int N = 510,INF=1e9;

int g[N][N];//g[i][j] Record i->j Shortest path 

int n,m,Q;

void floyd(){
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
            }
        }
    }
}

int main(){
    cin>>n>>m>>Q;
    for(int i=1;i<=n;i++){// Initialize array 
        for(int j=1;j<=n;j++){
            if(i==j) g[i][j]=0;
            else g[i][j]=INF;
        }
    }
    while(m--){// Input m side 
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b]=min(g[a][b],c);
    }
    
    
    floyd();
    
    while(Q--){//Q Queries 
        int a,b;
        cin>>a>>b;
        if(g[a][b]>INF/2) cout<<"impossible"<else cout<return 0;
}

Algorithm analysis ： Triple cycle ,floyd The time complexity of the algorithm is O(n)O(n)O(n)

• The shortest path problem of graphs Detailed breakdown

• 1. Classification of shortest path problem in graph

• 2. Single source shortest path problem

• 2.1 When the edge weights are all positive

• 2.1.1 simple Dijstra Algorithm

• 2.1.2 Heap optimized Dijstra Algorithm

• 2.2 When the edge weights are negative

• 2.2.1 Bellman-ford Algorithm

• 2.2.2 SPFA Algorithm

• 3. Multi source sink shortest path problem

• Floyd Algorithm

  __EOF__

  Guagua - Link to this article ：https://blog.csdn.net/xiaodaiguagua/p/16364893.html

• About bloggers ： Comments and private messages will be answered as soon as possible . perhaps Direct personal trust I .
• Copyright notice ： All articles in this blog except special statement , All adopt BY-NC-SA license agreement . Reprint please indicate the source ！
• Solidarity bloggers ： If you think the article will help you , You can click the bottom right corner of the article **【[ recommend ](javascript:void(0)】** once .