Décomposition détaillée du problème de chemin le plus court du graphique

Problème de chemin le plus court du graphique Version détaillée décomposée

1.Classification des problèmes de chemin le plus court pour les graphiques

2.Problème de court - circuit à source unique

2.1Les poids latéraux sont tous positifs

2.1.1 SimpleDijstraAlgorithmes

Pensée algorithmique：Chaque fois qu'un noeud dont la distance la plus courte n'a jamais été déterminée trouve le noeud dont la distance la plus courte est la plus petite par rapport au point de départ,Rejoindre la collectionsMoyenne,Et mettre à jour d'autres chemins de noeud qui ne sont pas identifiés comme les chemins les plus courts avec ce noeud.Jusqu'à ce que la valeur de chemin la plus courte pour tous les noeuds finaux soit calculée,Ensemble maintenantsPour tous les noeuds.

#include<bits/stdc++.h>
using namespace std;

const int N = 510;
int g[N][N];//Carte dense,Stockage de la matrice de contiguïté
int st[N];//A - t - on déjà visité,C'est - à - dire sisEnsemble
int dist[N];//Noter la distance entre chaque point et le point de départ
int n,m;
//Le numéro de retour estnLe noeud de1Le chemin le plus court vers le noeud no
int dijstra(){
    memset(dist,0x3f,sizeof dist);//Initialiser la distance à l'infini
    dist[1]=0;//1 La distance du noeud no est initialisée à 0
    for(int i=0;i<n;i++){//nCycle de rotation, Trouver un noeud à la fois ,AdhésionsEnsemble, Et mettre à jour d'autres noeuds avec distTableau.Il doit y en avoir un.nCycle de rotation,Parce que pour mettre à jourdistTableau
        int t=-1;
        for(int j=1;j<=n;j++){// Boucle pour trouver la distance actuelle 1 Le noeud numéro un est le plus proche , Et n'a pas rejoint sNode of
            if(!st[j]&&(t==-1||dist[j]<dist[t])){
                t=j;
            }
        }
        st[t]=true;// Ajouter ce noeud à sTableau
        for(int j=1;j<=n;j++){// Boucle pour mettre à jour d'autres distances de noeud 
            if(!st[j]){
                dist[j]=min(dist[j],dist[t]+g[t][j]);
            }
        }
    }
    if(dist[n]==0x3f3f3f3f) return -1;//Sidist[n]Non mis à jour, Indique qu'il n'est pas accessible 
    return dist[n];
}

int main(){
    memset(g,0x3f,sizeof g);// La distance entre les noeuds d'initialisation est infinie 
    cin>>n>>m;// Les données d'entrée contiennent nNoeuds,mBordure
    int a,b,c;
    while(m--){
        cin>>a>>b>>c;//EntréemBordure, Les données d'entrée ont des anneaux et des bords doubles ,Prenez le minimum
        g[a][b]=min(g[a][b],c);
    }
    cout<<dijstra()<<endl;
    return 0;
}

Analyse des algorithmes： L'algorithme contient deux cycles ,La complexité temporelle est\(O(n^2)\)

2.1.2 Pile optimiséeDijstraAlgorithmes

Idées d'optimisation：SimpleDijstra L'algorithme doit trouver le noeud le plus proche du point de départ à chaque fois ,Rejoindre la collectionsMoyenne. Nous pouvons utiliser le tas pour maintenir la distance entre les noeuds et le point de départ , Pour éviter un double cycle .

// Un graphique clairsemé dijstra
#include<bits/stdc++.h>
using namespace std;

const int N = 1.5e5+10;

int e[N],ne[N],w[N],h[N],idx;//Graphique clairsemé,Stockage avec liste de contiguïté

int n,m;//nNoeuds,mBordure

int dist[N];//Tableau des distances
bool st[N];//Oui Non,C'est - à - dire:s Ensemble de balises 

typedef pair<int, int> PII;// Utiliser le tri automatique heap ,pairDefirstDistance,secondNo.

void add(int a,int b,int c){//Ajouter un noeuda->bLe bord de,Les poids sontc
    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<PII,vector<PII>,greater<PII>> q;// Déclarez un petit tas de racines 
    q.push({0,1});//1 Noeud n° 1 dans la file d'attente 
    while(!q.empty()){
        PII t=q.top();
        q.pop();
        int distance=t.first,x=t.second;
        if(st[x]) continue;// La distance a été déterminée ,Skip
        st[x]=true;
        for(int i=h[x];i!=-1;i=ne[i]){
            int j=e[i];
            if(dist[x]+w[i]<dist[j]){
                dist[j]=dist[x]+w[i];
                q.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()<<endl;
    return 0;
}

Analyse des algorithmes：
Complexité temporelle： Mettre à jour les autres points le long des bords chaque fois qu'un point avec une distance minimale est trouvé ,Sidist[j] > distance + w[i],Indique qu'il peut être mis à jourdist[j], Mise à jour avant j Le point et la distance correspondante sont placés dans un petit tas de racines . Parce que le nombre de points est n, Le nombre de côtés est m,Dans les cas extrêmes（Carte dense\(m=\frac{n*n(n-1)}{2}\)） Peut être mis à jour jusqu'à mRetour, Jusqu'à un maximum de mises à jour par tour \(n^2\)Un point（ Techniquement, c'est n - 1Un point）,Oui.mRetour, Donc, au plus \(n^2\) Placer les points dans le petit tas de racines , Donc chaque fois que vous mettez à jour le tri des petits tas de racines \(O(log(n^2))\),C'est le plus grand.mMises à jour, La limite supérieure de complexité temporelle totale est donc \(O(mlog((n^2)))=O(2mlogn)=O(mlogn)\)
Questions： Pourquoi la distance existe - t - elle? ？
Parce que la dernière fois que vous avez rejoint la collection s Éléments mis à jour pour aValeur de distance pour, Mais la distance est grande ,Jusqu'àa La distance de popSors de là..

2.2 Cas où le poids de bord est négatif

2.2.1 Bellman-fordAlgorithmes

Pensée algorithmique： S'il y a nUn point,Alors, aprèsn-1Sous - cycle, Desserrer chaque bord à chaque cycle ,Si n-1 Il peut être mis à jour après le relâchement secondaire,Indique qu'il y a un anneau négatif dans le diagramme,Par conséquent, aucun résultat n'a pu être obtenu.,Sinon, c'est fini.
Opération de relaxation：

for nUne fois
	for Tous les côtés a,b,w (Opération de relaxation)
		dist[b] = min(dist[b],back[a] + w)

Attention!：back[] Le tableau est après la dernière itération dist[] Sauvegarde du tableau,Parce que c'est chaque point qui part en même temps,Il faut donc dist[] Tableau de sauvegarde,L'effet de concaténation se produit si aucune sauvegarde n'est effectuée,Affecte le point suivant.

Dans le code suivant,Est accessiblenLe jugement du point n° doit être effectuéif(dist[n] > INF/2)Jugement,Et nonif(dist[n] == INF)Jugement,La raison en est queINFEst une valeur déterminée,Pas vraiment infini,Sera affecté par d'autres valeurs,dist[n]Plus grand queINFUn nombre du même ordre de grandeur suffit.

bellman - ford L'algorithme est bon pour résoudre le problème de court - circuit limité par le nombre de bords .

// Ce code résout le problème du chemin le plus court avec des limites de bord 
#include<bits/stdc++.h>
using namespace std;

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

struct{
    int a,b,w;
}edges[N];//a->bIl y a un côté,Le poids estw

int bellman_ford(){
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    for(int i=0;i<k;i++){//La plupartkBordure, Au total, la meilleure façon de passer kBordure
        memcpy(backup,dist,sizeof dist);
        for(int j=0;j<m;j++){//Pour tousm Les bords des bandes se détendent 
            int a=edges[j].a,b=edges[j].b,w=edges[j].w;
            if(backup[a]+w<dist[b]){
                dist[b]=backup[a]+w;
            }
        }
    }
    if(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<m;i++){
        cin>>a>>b>>w;
        edges[i]={a,b,w};
    }
    int ans=bellman_ford();
    if(ans==-0x3f3f3f3f){
        cout<<"impossible"<<endl;
    }else{
        cout<<ans<<endl;
    }
    
    return 0;
}

Analyse des algorithmes：
Complexité temporelle：\(O(nm)\),Parmi euxnNombre de points,mEst le nombre de côtés

2.2.2 SPFAAlgorithmes

Pensée algorithmique：OptimiséBellman-fordAlgorithmes.InBellman-fordDans l'algorithme,dist[b] = min(dist[b],back[a] + w),Sia La distance n'a pas été mise à jour , Donc mon cycle a fait beaucoup de choses inutiles . Donc nous voulons être a Lorsque la distance est mise à jour ,Encore une fois.a Mettre à jour les valeurs de distance pour les autres noeuds . L'idée de l'algorithme est similaire à DijstraAlgorithmes.

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5+10;

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

int n,m;

int st[N];// Si le noeud d'enregistrement est dans la file d'attente , C'est - à - dire si une mise à jour a eu lieu 
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]){//Opération de relaxation
                dist[j]=dist[t]+w[i];
                if(!st[j]){// Mise à jour de la distance du noeud , Vous pouvez donc utiliser ce noeud pour mettre à jour d'autres noeuds 
                    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"<<endl;
    else cout<<ans<<endl;
    return 0;
}

Analyse des algorithmes：
Bellman_fordEnfin, dans l'algorithmereturn -1La condition de jugement dedist[n]>0x3f3f3f3f/2;EtspfaL'algorithme écritdist[n]==0x3f3f3f3f;La raison en est queBellman_fordL'algorithme traverse tous les bords,Donc, qu'il s'agisse ou non d'un bord relié au point source, il est mis à jour;MaisSPFALes algorithmes sont différents,C'est l'équivalent deBFS, Ainsi, les noeuds traversés sont connectés au point source , Donc si vous demandez nDéconnecté du point source,Il ne sera pas mis à jour,Toujours en attente0x3f3f3f3f.

Bellman_fordL'algorithme peut avoir une boucle de poids négatif,C'est parce que le nombre de cycles est limité qu'il n'y a pas de cycle de vie ou de mort;MaisSPFAL'algorithme ne peut pas,Parce que la file d'attente est utilisée pour stocker,Chaque fois qu'il y a des mises à jour, il y a toujours des files d'attente.,Donc s'il y a un circuit négatif, ne l'utilisez pas.SPFASinon, le cycle de la mort.

Parce queSPFAL'algorithme est basé surBellman_fordL'algorithme est optimisé,Dans le pire des cas, la complexité temporelle est la même que celle - ci, c'est - à - dire que la complexité temporelle est \(O(nm)\) ,Si le temps de la question le permet, il peut être utilisé directementSPFAAlgorithme pour résoudreDijkstraLe titre de l'algorithme.

L'anneau négatif est généralement utiliséSPFAAlgorithmes, La méthode est d'utiliser un cntLe tableau enregistre le nombre de bords par point à la source,Un point est mis à jour une fois+1,Une fois que le nombre de bords a atteintnCela prouve l'existence d'un anneau négatif.

3. Problème de chemin le plus court pour les puits multisources

FloydAlgorithmes

Pensée algorithmique：Triple cycle,Idées de programmation dynamique.\(dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])\)

#include<bits/stdc++.h>
using namespace std;

const int N = 510,INF=1e9;

int g[N][N];//g[i][j]Enregistrementi->jLe chemin le plus court vers

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++){//Initialiser le tableau
        for(int j=1;j<=n;j++){
            if(i==j) g[i][j]=0;
            else g[i][j]=INF;
        }
    }
    while(m--){//EntréemBordure
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b]=min(g[a][b],c);
    }
    
    
    floyd();
    
    while(Q--){//QRequête secondaire
        int a,b;
        cin>>a>>b;
        if(g[a][b]>INF/2) cout<<"impossible"<<endl;
        else cout<<g[a][b]<<endl;
    }
    
    return 0;
}

Analyse des algorithmes：Triple cycle,floydLa complexité temporelle de l'algorithme est\(O(n)\)