概述

• 迪杰斯特拉算法是一种广为人知的最短路径算法，下面叫做Dijkstra；
• Dijsktra和BFS的本质区别在于BFS是按照人为预先定义好的顺序访问容器中的节点，而Dijsktra是访问当前容器中累计成本最低的节点，累计成本为g(n)；
• Dijsktra算法使用了动态规划的思想；
• Dijkstra算法可以保证它访问的节点是当前时刻容器中代价最小的节点，因此保证了算法的完备性；

思路

• 路径数组map[ ][ ]，开闭数组vis[ ]（蓝点0白点1），最短路径数组dis[ ]（初始化全为无穷大，开始点为0）
• 定义蓝点0（未找到最短路径点）、白点1（已找到最短路径点）
• 每次从蓝点中取出dis最小的点minPoint，将其置为白点，然后遍历if(!vis[i] && dis[i] > dis[minPoint] + map[minPoint][i])则更新dis[i]
• 当所有点都为白点，则退出循环

代码实现

// djistra 代码实现
// 求源点 s 到其他点的最短路径
void dijstra (int s)
{
    // 初始化 dis 默认值为无穷大
    vector<int> dis(n, MAX_INT);
    // 源点的 dis 为 0
    dis[s] = 0;
    while (true)
    {
        int minPoint = 0;
        for (int i = 1; i <= n; i++)
        {
            // 从蓝点中找到 dis 最小的点
            if (!vis[i] && _min > dis[i])
            {
                minPoint = i;
                _min = dis[i];
            }
        }
        // 如果没有蓝点 说明结束
        if (minPoint == 0)
            break;
        // 将当前点设置为白点
        vis[minPoint] = 1;
        // 遍历所有点
        for (int i = 1; i <= n; i++)
        {
            // 如果当前点为蓝点且当前点路径大于从minPoint到当前点路径 则更新
            if (vis[i] == 0 && dis[i] > dis[minPoint] + map[minPoint][i])
            {
                dis[i] = dis[minPoint] + map[minPoint][i];
            }
        }
    }
}

优缺点

Dijkstra优点

可保证最优解

可以保证得到的节点一定是从起点开始到当前的最小代价的路径，因此按照这一原则进行搜索，当发现目标节点后，回溯出的路径一定是最小代价的路径，即保证算法的完备性。

Dijkstra缺点

要向所有方向扩展，效率不高

Dijkstra不知道目标节点位置，只能保证每一步得到的节点累计代价g(n)是最小的，它必须要向所有方向扩展，目的性不强，导致算法的效率也不高。

参考资料