Dijkstra迪杰斯特拉算法及C++实现

Dijkstra算法是典型的最短路径路由算法，用来计算一个节点到其他所有节点的最短路径。算法的基本思想和流程是：
1. 初始化出发点到其它各点的距离dist[]以及各点的前一个访问点pre[]；
2. for(i=2…n){
　　找出dist[]中未访问过点中的最小值，记录为best；
　　以dist[best]为基准更新dist[]；
　　更新pre[]；
}

从1出发，第一次找到最小点2，更新dist[]，然后找到最小点4，以此类推，以当前最小为最优（贪心算法），列出下表：

具体实现：

#include <iostream>

#include <vector>

const int maxdist = 114514;

using namespace std;

/*n是总的结点数,v是出发结点,dist是距离,pre前一个结点,d是结点间的权值*/

void Dijkstra(int n, int v, vector<int> &dist, vector<int> &pre, vector<vector<int>> &d){

    vector<bool> s(n+1);

    for (int i = 1; i <= n;i++){

        dist[i] = d[v][i];

        if (dist[i] < maxdist)

            pre[i] = v;

        else

            pre[i] = 0;

    }

    dist[v] = 0;

    s[v] = true;

    for (int i = 2; i <= n;i++){//总迭代次数

        int best = v;

        int temp = maxdist;

        for (int j = 1; j <= n;j++){//找到最小的距离

            if (!s[j]&&dist[j]<temp){

                temp = dist[j];

                best = j;

            }

        }

        s[best] = true;

        for (int j = 1; j <= n;j++){//更新dist和pre

            if (!s[j] && d[best][j] != maxdist){

                int newdist = dist[best] + d[best][j];

                if (newdist<dist[j]){

                    dist[j] = newdist;

                    pre[j] = best;

                }

            }

        }

    }

}

void printpath(vector<int> pre, int init, int fina){

    int temp=fina;

    vector<int> t;

    while (temp != init){

        t.push_back(temp);

        temp = pre[fina];

        fina = temp;

    }

    cout << init << "->";

    for (int i = t.size(); i >1;i--)cout << t[i-1] << "->";

    cout << t[0];

    t.clear();

}

int main(){

    int n, l;

    cout << "请输入结点数和线数：";

    cin >> n >> l;

    vector<vector<int>> d(n+1, vector<int>(n+1));

    for (int i = 1; i <= n;i++){

        for (int j = 1; j <= n; j++)

            d[i][j] = maxdist;

    }

    int p, q, len;

    for (int i = 1; i <= l; ++i){

        cin >> p >> q >> len;

        if (len < d[p][q]){       // 有重边

            d[p][q] = len;      // p指向q

            d[q][p] = len;      // q指向p，这样表示无向图

        }

    }

    vector<int> dist(n+1),pre(n+1);

    for (int i = 1; i <= n; ++i)dist[i] = maxdist;

    Dijkstra(n, 1, dist, pre, d);

    cout << "点1到点n的最短路径长度: " << dist[n] << endl;

    cout << "点1到点n的路径为: ";

    printpath(pre, 1, n);

    return 0;

}

Dijkstra（迪杰斯特拉）算法C++实现&讲解的相关教程结束。