最短路径算法

1.求单源最短路径(某个点到其余各点的最短路径)——迪杰斯特拉算法

//只经过一个顶点任意两个顶点的最短路径问题
for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
       if(e[i][j]>e[i][1]+e[1][j])
           e[i][j]=e[i][1]+e[1][j];
   }
}

1.初始化e数组

2.读入边

3.初始化dis数组

#include
using namespace std;
int main() {
    int e[10][10], dis[10], book[10],n,m;
    int inf = 99999999;
    cin >> n >> m;
    //初始化
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j)e[i][j] = 0;
            else e[i][j] = inf;
        }
    }
    //读入边
    int v1, v2, w;
    for (int i = 1; i <= m; i++) {
        cin >> v1 >> v2 >> w;
        e[v1][v2] = w;
    }
    //初始化dis数组
    for (int i = 1; i <= n; i++) {
        dis[i] = e[1][i];
    }
    book[1] = 1;
    //迪杰斯特拉算法的核心
    for (int i = 1; i <= n - 1; i++) {
        int min = inf,u;
        for (int j = 1; j <= n; j++) {
            if (book[j] == 0 && dis[j] < min) {
                min = dis[j];
                u = j;
            }
        }
        book[u] = 1;
        for (int v = 1; v <= n; v++) {
            if (e[u][v] < inf) {
                if (dis[v] < dis[u] + e[u][v]) {
                    dis[v] = dis[u] + e[u][v];
                }
            }
        }
    }
    //输出最终的结果
    for (int i = 1; i <= n; i++) {
        cout << dis[i] << " ";
    }
    return 0;
}

2.求每队顶点间的最短路径（任意两点的最短路径）——弗洛伊德算法

1.初始化e数组 2.读入边

//经过所以顶点作为中转，任意两点之间最终的最短路径
for(int k=1;k<=n;k++){
    for(int i=1;i<=n;i++){
       for(int j=1;j<=n;j++){
            if(e[i][j]>e[i][k]+e[k][j]
              e[i][j]=e[i][k]+e[k][j];
         
       } 
   }
}

#include
using namespace std;
int main() {
    int e[10][10], k, i, j, n, m, t1, t2, t3;
    int inf = 99999999;
    cin >> n >> m;
    //初始化
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j)e[i][j] = 0;
            else e[i][j] = inf;
        }
    }
    //读入边
    for (int i = 1; i <= n; i++) {
        cin >> t1 >> t2 >> t3;
        e[t1][t2] = t3;
    }

    //弗洛伊德算法核心语句
    for (k = 1; k <= n; k++) {
        for (i = 1; i <= n; i++) {
            for (j = 1; j <= n; j++) {
                if (e[i][j] > e[i][k] + e[k][j]) {
                    e[i][j] = e[i][k] + e[k][j];
                }
            }
        }
    }

    //输出最终的结果
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            cout << e[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}