一、简介

将结点分成两个集合：已确定最短路长度的点集（记为 S 集合）的和未确定最短路长度的点集（记为 T 集合）。一开始所有的点都属于 T 集合。

初始化 dis(s) = 0 ，其他点的 dis 均为 +\infty 。

然后重复这些操作：

  1. 从 T 集合中，选取一个最短路长度最小的结点，移到 S 集合中。
  2. 将到刚刚被加入 S 集合的节点的最短路加上到与其相连的节点 s 的距离与到 s 的最短路比较，短的更新为 s 的最短路。

直到集合 T 为空,算法结束。

二、代码

struct edge
{
    int node;
    int val;
};

vector<vector<edge>> edges(num + 1); //创建邻接表,忽略下标0
vector<int> dis(num + 1,MAX); //第i个节点到源节点的最大值,初始为MAX
vector<bool> vis(num + 1,0); //节点是否被访问，初始为否

void dijkstra(int num,int start,vector<vector<edge>> &edges,vector<int> &dis,vector<bool> vis)
{
    dis[start] = 0; //到源节点到源节点的最大值为0
    //寻找所有节点到源节点的最小路径
    for(int i = 1;i <= num;i++)
    {
        int tmpIndex = 0;
        int tmpVal = MAX;
        //寻找dis中未访问节点的最小值
        for(int j = 1;j <= num;j++)
        {
            if(!vis[j] && dis[j] < tmpVal)
            {
                tmpIndex = j;
                tmpVal = dis[j];
            }
        }
        vis[tmpIndex] = 1;
        //更新dis中未访问节点的距离
        for(auto edge : edges[tmpIndex])
        {
            if(dis[edge.node] > dis[tmpIndex] + edge.val)
            {
                dis[edge.node] = dis[tmpIndex] + edge.val;
            }
        }
    }
}

三、参考链接

OI Wiki : https://oi-wiki.org/graph/shortest-path/#dijkstra-算法