Dijkstra算法笔记与思路整理

该文章可能存在硬伤与不妥，不能作为教程阅读。（因为我真的鶸

Dij作为单源最短路算法，需要先确定一个起点。Dij的函数主体为维护每个节点的dis和vis两个变量。dis表示该点距离起点的最短路权值和，vis存储该点是否被访问过。

设点数为n，无向边数为m，则要进行n次循环，每次循环中找出一个dis最小且vis不为真的点进行松弛操作。

这里抄一段百科：

松弛操作是指对于每个顶点v∈V，都设置一个属性g[v]，用来描述从源点s到v的最短路径上权值的上界，称为最短路径估计(shortest-path estimate)。

松弛操作主要代码：

if(dis[g[i].to] > g[i].val + curr.dis)

    dis[g[i].to] = g[i].val + curr.dis;

然后就是优化：

　　(1)判断最小值的循环可用优先队列优化

　　(2)使用优先队列后可以直接判断堆中是否剩余元素来循环

　　(3)使用链表存储图，松弛操作只遍历相关的边

模板：

#include <bits/stdc++.h>

#define maxn 10010

#define maxm 10010

using namespace std;

struct edge{

    int to, val, next;

};

edge g[maxm];

int first[maxn], edge_cnt = ;

struct node{

    int pos, dis;

};

priority_queue<node> q;

bool operator<(const node a, const node b){

    return a.dis > b.dis;

}

int dis[maxn], vis[maxn];

int n, m;

void in_put(){

    scanf("%d%d", &n, &m);    //n nodes, m edges

    for(int i=; i<m; i++){

        int f, t, val;

        scanf("%d%d%d", &f, &val, &t);

        g[edge_cnt] = (edge){t, val, };

        g[edge_cnt].next = first[f];

        first[f] = edge_cnt;

        edge_cnt ++;

    }

}

void dijkstra(int start){

    vis[start] = ;

    dis[start] = ;

    q.push((node){start, dis[start]});

    while(q.size()){

        node curr = q.top();

        q.pop();

        int from = curr.pos;

        for(int i = first[from]; i ; i = g[i].next){

            if(dis[g[i].to] > g[i].val + curr.dis){

                dis[g[i].to] = g[i].val + curr.dis;

                q.push((node){g[i].to, dis[g[i].to]});

            }

        }

    }

}

int main(){

//    freopen(".in", "r", stdin);

//    freopen(".out", "w", stdout);

    memset(dis, 0x3f, sizeof(dis));

    in_put();

    dijkstra();

    return ;

}

巴特西

Dijkstra算法笔记与思路整理

最新文章

热门文章

巴特西

Dijkstra算法 笔记与思路整理

最新文章

热门文章

Dijkstra算法笔记与思路整理