理解最短路径——迪杰斯特拉（dijkstra）算法

原文链接：http://ibupu.link/?id=29

/* 大家可以先看大神的理论知识，将dijkstra思想搞懂，然后在 来看我举得简单的例子 */

输入输出

输入：
v e
e行 ，每行表示俩个节点相连的边的长度
输出：
节点1的单源最短路径
input：
6 9
1 2 7
1 3 9
1 6 14
2 3 10
2 4 15
3 4 11
3 6 2
4 5 6
5 6 9
output：
0 7 9 20 20 11
大神里面的那个图的例子

代码实现

#include<iostream>
#include<cstring>
using namespace std;
const int MAXN = 100;
const int INF = 10000;
int w[MAXN][MAXN]; //存图，相连节点之间的边 ，无边初始化为最大值 
int vis[MAXN]; //标记节点是否使用过 
int dis[MAXN]; //存起点到终点的最短路径数组 

void dijkstra(int n)
{ 
    //n节点的个数，节点为1--n
    //这里假设求 起点为节点1到其他节点的最短路径
    //分为俩个区域，更新过的区域x，未更新的区域y
    //将节点1加入x 
    //第一步，初始化dis数组，并且标记节点1为1.用过 
    for(int i=2; i<=n; ++i)
        dis[i] = w[1][i];     
    vis[1] = 1;
    //第二步，依次找个节点加入x，更新x，y区域 
    for(int i=2; i<=n; ++i)
    {
        int MIN = INF, k;
        //找与节点1有边相连的最短节点记为k，最短记为MIN 
        for(int j=1; j<=n; ++j)
        {
            if(!vis[j] && MIN > dis[j])
            {
                MIN = dis[j];
                k = j;
            }
        }
        vis[k] = 1; //将节点k加入x
        //更新y区域 
        for(int j=1; j<=n; ++j)
        {
            if(!vis[j] && MIN+w[k][j] < dis[j])
            {
                dis[j] = MIN + w[k][j];
            }
        }       
    }
}
int main()
{
   //将数组全部初始化为最大值
    for(int i=0; i<MAXN; ++i)
        for(int j=0; j<MAXN; ++j)
            w[i][j] = INF;

    memset(vis, 0, sizeof(vis));
    memset(dis, 0, sizeof(dis));
    int v , e; // v 节点， e边 
    while(cin >> v >> e)
    {
       int j, k , len;
       //初始化图数组 
       for(int i=0; i<e; ++i)
       {
           cin >> j >> k >>len;
           w[j][k] = w[k][j] = len;
       }
        dijkstra(v); 
        for(int i=1; i<=v; ++i)
            cout << dis[i] << " ";
    }
    return 0;
}