@jtahstu 2017-09-30T10:14:53.000000Z 字数 1077 阅读 2246

# 单源最短路径算法 - Dijkstra算法

算法

## 代码

/** * 单源最短路径算法 * Dijkstra算法 * 时间复杂度 O(N^2) * by jtahstu at 2017-09-18 */#include <iostream>#include <climits>using namespace std;int main() {    int n, m;    cin >> n >> m;    int e[11][11] = {0}, dis[11] = {0}, book[11] = {0};    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] = INT_MAX;    int a, b, c;    for (int i = 1; i <= m; i++) {        cin >> a >> b >> c;        e[a][b] = c;    }    for (int i = 1; i <= n; ++i) {        dis[i] = e[1][i];        book[i] = 0;    }    book[1] = 1;    int min, u;    for (int i = 1; i <= n - 1; ++i) {  //找出值最小的点去做中转，循环n-1次        min = INT_MAX;        for (int j = 1; j <= n; j++) {  //找到离1号顶点最近的顶点，然后该点最短路径值确定            if (book[j] == 0 && min > dis[j]) {                min = dis[j];                u = j;            }        }        book[u] = 1;    //标记该点最短路径值已经确定        for (int v = 1; v <= n; v++) {            if (dis[v] > dis[u] + e[u][v] && e[u][v] != INT_MAX) //有出边，且可以通过u点中转一下                dis[v] = dis[u] + e[u][v];        }    }    for (int i = 1; i <= n; i++)        cout << dis[i] << " ";    return 0;}/**6 81 2 11 3 22 3 32 4 32 5 13 4 54 6 25 6 10 1 2 4 2 36 91 2 11 3 122 3 92 4 33 5 54 3 44 5 134 6 155 6 40 1 8 4 13 17 */

• 私有
• 公开
• 删除