最短路径C++，Dijkstra

Description

给出一个有向图（无负权值），求任意两点间的最短路径

Input

第一行为有向图中点的数量n（各点从0到n-1编号）第二行为边的数量m第三行为要求其间最短路径的两个点第四行起为m条边的信息，包括起点、终点和路径长度（保证长度是整数，且绝对值不大于100），以空格隔开

8

15

0 5

4 5 35

5 4 35

4 7 37

5 7 28

7 5 28

5 1 32

0 4 38

0 2 26

7 3 39

1 3 29

2 7 34

6 2 40

3 6 52

6 0 58

6 4 93

Output

求出输入中第三行两个点之间的最短路径长度并输出，比如上面的输入例子中，点0到点5间最短路径长度为73，则输出为：73

Sample Input 1 

8
15
0 5
4 5 35
5 4 35
4 7 37
5 7 28
7 5 28
5 1 32
0 4 38
0 2 26
7 3 39
1 3 29
2 7 34
6 2 40
3 6 52
6 0 58
6 4 93

Sample Output 1

73

Hint

保证n小于1000，且答案不超过 10^5.

来源：广西大学OJ

思路

最短路径有dijkstra和floyd算法，floyd算法时间复杂度是n的三次方，n小于10^5，显然超时，只能用dijkstra

#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int dist[1000][1000];
int n, m, start, finish;
bool visited[1000];

void dijkstra() {
    // 初始化距离数组，除了起点到自身距离为0，其余为无穷大
    dist[start][start] = 0;

    for (int i = 0; i < n; ++i) {
        int minDist = INF, minIndex = -1;
        // 找到当前未访问节点中距离起点最近的节点
        for (int j = 0; j < n; ++j) {
            if (!visited[j] && dist[start][j] < minDist) {
                minDist = dist[start][j];
                minIndex = j;
            }
        }

        if (minIndex == -1) break;
        visited[minIndex] = true;

        // 更新与该节点相邻节点的距离
        for (int k = 0; k < n; ++k) {
            if (!visited[k] && dist[minIndex][k]!= INF) {
                int newDist = dist[start][minIndex] + dist[minIndex][k];
                if (newDist < dist[start][k]) {
                    dist[start][k] = newDist;
                }
            }
        }
    }
}

int main() {
    cin >> n;
    cin >> m;
    cin >> start >> finish;

    // 初始化邻接矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dist[i][j] = INF;
        }
    }

    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        dist[u][v] = w;
    }

    dijkstra();
    cout << dist[start][finish] << endl;

    return 0;
}

floyd，超时了，可以参考

#include<bits/stdc++.h>
using namespace std;
int dist[1000][1000];
int n, m,start,finish;

void Floyd(int num) {
    for (int k = 0; k < num; k++) {
        for (int i = 0; i < num; i++) {
            for (int j = 0; j < num; j++) {
                if (dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
}

int main() {

    cin>>n;
    cin>>m;
    cin>>start>>finish;
    //初始化，不可达距离大于100（题目数据），到自己距离0
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i != j) {
                dist[i][j] = 101;
            } else {
                dist[i][j] = 0;
            }
        }
    }
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin>>u>>v>>w;
        dist[u][v] = w;
    }
    Floyd(n);
    cout<<dist[start][finish];
    return 0;
}

原文地址：https://blog.csdn.net/m0_74074965/article/details/144735875

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！