最短路径三种解法

基础最短路模板:

有 n 个人,他们的编号为 1~n,其中有一些人相互认识,现在 x 想要认识 y,可以通过他所认识的人来认识更多的人
(如果 x 认识 y、y 认识 z,那么 x 可以通过 y 来认识 z),求出 x 最少需要通过多少人才能认识 y。
【输入格式】
第 1 行 3 个整数 n、x、y,n≤100,1≤x、y≤n。
接下来是一个 n×n 的邻接矩阵,a[i][j]=1 表示 i 认识 j,a[i][j]=0 表示不认识。
保证 i=j 时,a[i][j]=0,并且 a[i][j]=a[j][i]。
【输出格式】
输出一行一个数,表示 x 认识 y 最少需要通过的人数。
【样例输入】

5 1 5
0 1 0 0 0
1 0 1 1 0
0 1 0 1 0
0 1 1 0 1
0 0 0 1 0
【样例输出】
2

#include<bits/stdc++.h>
using namespace std;
/*
    1.可以直接跑BFS

    2.无向图最短路径,因为只有输入只有一次查询,那么dijkstra,spfa都可以
            dijkstart:因为权值全都为1,所以就不用考虑堆优化.

    3.还有一种多源不含负权最短路径,floyd 算法,时间复杂度0(n^3),填空题可以使用一下
            借用的是动态规划的思路

*/
int u[105][105];
int n,X,Y;

int bfs(){
    queue<pair<int,int>>que;//先进先出,对于每一个条路线需要记录所走的路径长度
    vector<int>judg(n+1,0);//标记数组
    que.push({X,0});

    while(!que.empty()){
        pair<int,int> k=que.front();
        que.pop();
        if(k.first==Y){
            return k.second-1;//访问到时走的路程-1就是访问的人数
        }
        if(judg[k.first])continue;//标记点,防止反复访问同一个点
        judg[k.first]=1;
        for(int i=1;i<=n;i++){
            if(i!=k.first&&u[k.first][i]==1){
                if(!judg[i]){
                    que.push({i,k.second+1});
                }
            }
        }
    }

    return 0;
}

//单源最短路径,不含负权
int dijkstra(int x){
    /*
        在权值不同的时候,每次取队首的元素,优化到保证是里面最小的,需要把队列改成优先队列
    */
    vector<int>ans(n+1,INT_MAX/2);//ans[i]记录x到i的距离
    vector<int>judg(n+1,0);//标记数组,保证点只被访问一次

    queue<int>que;
    que.push(x);
    ans[x]=0;
    while(!que.empty()){
        int k=que.front();
        que.pop();
        if(judg[k])continue;//被标记过
        judg[k]=1;
        for(int i=1;i<=n;i++){
            //if 保证不是自己到自己  k->i存在边
            if(k!=i&&u[k][i]==1&&ans[i]>ans[k]+1){//更新距离,如果x->i的距离大于x->k->i,就跟新
                ans[i]=ans[k]+1;
                if(!judg[i]){   //满足没有被访问过,加入队列
                    que.push(i);
                }
            }
        }
    }
    return ans[Y]-1;//

}

//包含负权,特判是否存在负环
int spfa(int x){
    vector<int>ans(n+1,INT_MAX/2);//ans[i]记录x到i的距离,类似于dijkstra
    vector<int>judg(n+1,0);//标记数组,保证队列内不存在重复的点
    vector<int>e(n+1,0);   //特判数组,表示每个点入栈多少次,如果超过总点数就说明存在负环,一直循环

    queue<int>que;
    que.push(x);//进队
    ans[x]=0;
    e[x]++;
    while(!que.empty()){
        int k=que.front();
        que.pop();
        if(e[k]>n)return false;//存在负环,找不到答案
        judg[k]=false;//不存队列中了

        for(int i=1;i<=n;i++){
            if(k!=i&&u[k][i]==1&&ans[i]>ans[k]+1){
                ans[i]=ans[k]+1;
                if(!judg[i]){  //不存在队列,加入
                    judg[i]=true;
                    e[i]++;
                    que.push(i);
                }
            }
        }
    }
    return ans[Y]-1;

}


//多源最短路径
int floyd(int x,int y){
    vector<vector<int>>ans(n+1,vector<int>(n+1,INT_MAX/2));//ans[i][j]表示i->j的距离
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            if(u[i][j]){
                ans[i][j]=1;//所有的距离都是1
            }
        }
    }

    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                if(ans[i][j]>ans[i][k]+ans[k][j]){
                    ans[i][j]=ans[i][k]+ans[k][j];
                }
            }
        }
    }
    return ans[x][y]-1;
}

int main(){

    scanf("%d%d%d",&n,&X,&Y);

    //编号从1开始,那么所有的都按1
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&u[i][j]);
        }
    }

//    printf("%d",bfs());
//    printf("%d",dijkstra(X));//求x->到所有的距离
//    printf("%d",spfa(X));      //求x->到所有的距离
    printf("%d",floyd(X,Y)); //x->y的距离
    return 0;
}
上一篇:剑指 Offer 32 - II. 从上到下打印二叉树 II(简单)


下一篇:leetcode 二叉搜索树层序遍历 中等