Dijkstra算法

分析

Dijkstra算法适用于边权为正的情况。它可用于计算正权图上的单源最短路（ Single-Source Shortest Paths， SSSP） ， 即从单个源点出发， 到所有结点的最短路（这样最后返回你想要的那个节点对应的距离即可）。 该算法同时适用于有向图和无向图。

其伪代码如下：

清除所有点的标号设d[0]=0， 其他d[i]=INF         //INF被定义为一个很大的数字循环n次 {在所有未标号结点中， 选出d值最小的结点x给结点x标记对于从x出发的所有边(x,y)， 更新d[y] = min{d[y], d[x]+w(x,y)}        //w(x,y)是指边xy对应的权值}

模板

可以根据上面的伪代码帮助理解

int Dijk(){    memset(vis, 0, sizeof(vis));    memset(d, 0, sizeof(d));    for(int i = 1; i <= N; i++)        d[i] = ((i == 1) ? 0 : INF);        //注意这里INF一定要设置的很大         //这里的条件设置根据题意自行判断    for(int i = 1; i <= N; i++)    {        int x, minn = INF;        for(int j = 1; j <= N; j++)        {            if(!vis[j] && d[j] < minn)          //在所有未标号结点中， 选出d值最小的结点x            {                minn = d[j];                x = j;            }        }        vis[x] = 1;           //标记它        for(int y = 1; y <= N; y++)            d[y] = min(d[y], d[x] + route[x][y]);    }    return d[...];              //根据题意要求进行返回相应的值}

以上内容参考自刘汝佳的《算法竞赛入门经典》

AC代码

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;const int maxn = 100 + 10;const int INF = 0x3f3f3f3f;int N, M;int a, b, c;int route[maxn][maxn], d[maxn];int vis[maxn];int Dijk(){    memset(vis, 0, sizeof(vis));    memset(d, 0, sizeof(d));    for(int i = 1; i <= N; i++)        d[i] = ((i == 1) ? 0 : INF);            //这里的条件设置根据题意自行判断    for(int i = 1; i <= N; i++)    {        int x, minn = INF;        for(int j = 1; j <= N; j++)        {            if(!vis[j] && d[j] < minn)          //在所有未标号结点中， 选出d值最小的结点x            {                minn = d[j];                x = j;            }        }        vis[x] = 1;           //标记它        for(int y = 1; y <= N; y++)            d[y] = min(d[y], d[x] + route[x][y]);    }    return d[N];}void init(){    for(int i = 1; i <= N; i++)    {        for(int j = i + 1; j <= N; j++)            route[i][j] = route[j][i] = INF;    }}int main(){//    freopen("input.txt", "r", stdin);//    freopen("output.txt", "w", stdout);    while(cin >> N >> M && N && M)    {        init();        for(int i = 0; i < M; i++)        {            cin >> a >> b >> c;            route[a][b] = route[b][a] = c;        }        int minn = Dijk();        cout << minn << endl;    }}