C++ 图论之最短路径

Floyd算法

应用：

附C++代码：

//
//  1447.cpp
//  最短路
//
//  Created by chenmeiqi on 2019/4/9.
//  Copyright © 2019年 chenmeiqi. All rights reserved.
//

#include <iostream>
using namespace std;
#define N 100
#define M 1001          // 题目中 C<=1000,所以 1001 代表无穷
int weight[N][N];
int main(int argc, const char * argv[]) {
    int n,m;
    int a,b;
    while(cin>>n>>m){
        if(n==0 && m==0){
            break;
        }
        for(int i = 0; i < N; i++)
        {
            for(int j = 0; j < N; j++)
            {
                weight[i][j]=M;             // 初始化
            }
            weight[i][i]=0;         //  自己到自己的路径长度设为0
        }
        
        
        while(m--){                 // 读入已有路径
            cin>>a>>b;
            cin>>weight[a-1][b-1];
            weight[b-1][a-1]=weight[a-1][b-1];
        }
        for(int k=0;k<n;k++){
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    if (weight[i][k]+weight[k][j]<weight[i][j]) {       // 经过 k 后获得了更短的路径，更新该值
                        weight[i][j]=weight[i][k]+weight[k][j];
                    }
                    
                }
            }
        }
        cout<<weight[0][n-1]<<endl;         // 第一个到最后一个结点的距离
    }
    return 0;
}

---

Dijkstra算法

改写：

//
//  1447.cpp
//  最短路径_Dijkstra
//
//  Created by chenmeiqi on 2019/4/9.
//  Copyright © 2019年 chenmeiqi. All rights reserved.
//

#include <iostream>
#include <vector>
using namespace std;
#define M 1001
struct E{
    int next;           // 直接相邻的结点
    int c;              // 该边的权值
};
vector<E> edge[101];        // 邻接链表
bool mark[101];     // 标记，当mask[j]为true时表示结点j的最短路径长度已经得到，该结点已经加入集合K
int Dis[101]; // 距离向量，当mask[i]为true时，表示已得到最短路径长度；否则，表示所有从结点1出发，经过已知的最短路径达到集合K中的某结点，再经过一条边到达结点i的路径中最短的距离
int main(int argc, const char * argv[]) {
    int n,m;
    while(cin>>n>>m){
        if(n==0&&m==0){
            break;
        }
        for(int i=1;i<=n;i++){
            edge[i].clear();            // 初始化邻接链表
        }
        while(m--){
            int a,b,c;
            cin>>a>>b>>c;
            E tmp;
            tmp.c=c;
            tmp.next=b;
            edge[a].push_back(tmp);
            tmp.next=a;
            edge[b].push_back(tmp);     //将邻接信息加入邻接链表，由于原图为无向图，故每条边信息都要添加到其两个顶点的单链表中
        }
        for(int i=1;i<=n;i++){
            Dis[i]=M;          // 所有距离为1001，即不可达
            mark[i]=false;      // 所有结点不属于集合K
        }
        Dis[1]=0;           // 得到最近的点为结点1，长度为0
        mark[1]=true;       // 将结点1加入集合K
        int newP=1;         // 集合K中新加入的点为结点1
        for(int i=1;i<n;i++){
            for(int j=0;j<edge[newP].size();j++){
                int t=edge[newP][j].next;
                int c=edge[newP][j].c;
                if(mark[t]==false){
                    if(Dis[newP]+c<Dis[t]){
                        Dis[t]=Dis[newP]+c;
                    }
                }
            }
            int min=M;
            for(int j=1;j<=n;j++){
                if(mark[j]==false && Dis[j]<min){
                    min=Dis[j];
                    newP=j;
                }
            }
            mark[newP]=true;
        }
        cout<<Dis[n]<<endl;
    }
    return 0;
}

对于vector模拟链表，见博主另一篇文章 https://blog.****.net/qq_36770641/article/details/88978758。

应用：

附C++代码：

//
//  1008.cpp
//  最短路径问题
//
//  Created by chenmeiqi on 2019/4/9.
//  Copyright © 2019年 chenmeiqi. All rights reserved.
//

#include <iostream>
#include <vector>
using namespace std;
#define N 1001
struct E{
    int next;
    int distance;
    int cost;
};
vector<E> edge[N];      // 邻接链表
int Dis[N];
int cost[N];
bool mark[N];
int main(int argc, const char * argv[]) {
    int n,m;
    int a,b,d,p;
    int s,t;            // 起点，终点
    while(cin>>n>>m){
        if(n==0 && m==0){
            break;
        }
        for(int i=1;i<=n;i++){      // 初始化
            edge[i].clear();
            Dis[i]=-1;
            cost[i]=0;
            mark[i]=false;
        }
        while(m--){             // 录入z已知信息
            cin>>a>>b>>d>>p;
            E e;
            e.next=b;
            e.distance=d;
            e.cost=p;
            edge[a].push_back(e);
            e.next=a;
            edge[b].push_back(e);
        }
        cin>>s>>t;
        Dis[s]=0;
        cost[s]=0;
        mark[s]=true;
        int newP=s;
        for(int i = 1; i < n; i++)
        {
            for(int j = 0; j < edge[newP].size(); j++)
            {
                int t=edge[newP][j].next;
                int d=edge[newP][j].distance;
                int c=edge[newP][j].cost;
                if(mark[t]==false){
                    if(Dis[t]==-1 || Dis[newP]+d<Dis[t] ||(Dis[newP]+d==Dis[t] && cost[newP]+c < cost[t])){     // 当距离更近或距离相等但花费更少时更新信息
                            Dis[t]=Dis[newP]+d;
                            cost[t]=cost[newP]+c;
                    }
                }
            }
            int min=123123123;
            for(int k=1;k<=n;k++){                  // 找到下一个最近点
                if(mark[k]==false && Dis[k]!=-1){
                    if(Dis[k]<min){
                        min=Dis[k];
                        newP=k;
                    }
                }
            }
            mark[newP]=true;
        }
        cout<<Dis[t]<<" "<<cost[t]<<endl;
    }
    return 0;
}