单源最短路——朴素Dijkstra&堆优化版

朴素Dijkstra 是一种基于贪心的算法。

稠密图使用二维数组存储点和边,稀疏图使用邻接表存储点和边。

算法步骤:

1.将图上的初始点看作一个集合S,其它点看作另一个集合

2.根据初始点,求出其它点到初始点的距离dist[i] (若相邻,则dist[i]为边权值;若不相邻,则dist[i]为无限大)

3.选取最小的dist[i](记为dist[x]),并将此dist[i]边对应的点(记为x)加入集合S(实际上,加入集合的这个点的dist[x]值就是它到初始点的最短距离)

4.再根据x,更新跟 x 相邻点 y 的dist[y]值:dist[y] = min{ dist[y], dist[x] + 边权值g[x] [y] },因为可能会把距离调小,所以这个更新操作叫做松弛操作
(仔细想想,为啥只更新跟x相邻点的dist[y],而不是更新所有跟集合 s 相邻点的 dist 值? 因为第三步只更新并确定了x点到初始点的最短距离,集合内其它点是之前加入的,也经历过第 4 步,所以与 x 没有相邻的点的 dist值是已经更新过的了,不会受到影响)

5.重复3,4两步,直到目标点也加入了集合,此时目标点所对应的dist[i]即为最短路径长度。

朴素版Dijkstra模板(时间复杂度为O(n²)):

int n, m;       //存储点数和边数
int g[][];      //存储图
int dist[];     //每个点到1号点的距离
bool v[];       //标记是否已经访问过该点

void dijkstra()
{
    memset( dist, 0x3f3f3f, sizeof v);
    dist[1] = 0;
    
    for( int i = 1; i <= n; i++)        //遍历每个点
    {
        int t = -1;
        for( int j = 1; j <= n; j++)    //找到未访问过的点
            if( !v[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        v[t] = true;                    //标记为已访问
        
        for( int j = 1; j <= n; j++)
            dist[j] = min( dist[j], dist[t]+g[t][j]);
    }
}

堆优化版Dijkstra模板(时间复杂度为O(m㏒n)):

typedef pair<int, int> PII;

const int N = 1e5 + 10;

int n, m;
int h[N], w[N], e[N], ne[N], idx;//单链表模拟邻接表存储图
int dist[N];                     //每个点到1号点的距离
bool st[N];

void add(int a, int b, int c)    //存储一个图
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;//模拟堆
    heap.push({0, 1});

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}
上一篇:P2764-最小路径覆盖问题


下一篇:杂谈-解读 | 《能力陷阱》