最短路算法(2)

2024-03-11 22:14:25

最短路算法(2)

1.基于BFS的无权图最短路径

如果是无权图，我们遍历一张图就可以得到一棵树，很显然，每个节点的深度就是它的的最短路径长度。
BFS搜图的过程类似于树的层次遍历。也就是说我们在BFS遍历时就可以得到最短路径。而不是完全搜索整个图。但是我们需要一个变量来记录遍历的深度。

2.有权图的最短路径算法（无负边）

一样是BFS，我们可以这么做：
我们从源点开始搜索，计算每一个邻居到源点的距离，并把这个距离放入一个数组 D。
接下来我们寻找最小的D。这条路径一定是最短路径。
因为后面的都是正边，加上来一定会增长路径。（这一句话便是这个算法不能处理负边的原因）
接下来我们再用刚刚得到的路径的终点来进行BFS。进行多次迭代。每次迭代都可以得到一条最短路径。
这样的算法是O(n*n)的，每次迭代都会得到一个点，进行n次迭代，每次找到最小值的时间花费为n。
如果我们使用优先队列，那么就会应该会找n个点和m条边。优先队列本身的插入时O(m)的，时间复杂度为O(mlogm),值得注意的是手写二叉堆的时间复杂度更好一些是O(mlogn)。
其实这就是dijkstra算法。

3.dijkstra的实现

在此之前，需要强调的是，O(n * n)不一定是比O(mlogn)差的，因为 m 与 n * n 应该是同阶的。接下来是紫书O( n * n)的dijkstra。

//初始化
for(int i = 1;i < n;i++)d[i]= inf;
d[0] = 0;
//主算法
for(int i = 0;i < n;i++){//n次迭代
     //每次遍历寻找d最小的结点，并且这个结点没有求出最短路径
     int x,m = inf;
     for(int j = 0;j < n;j++)
        if(!vis[i] && d[j] <= m)
           m = d[x=j];
     //当前最短的就是最短路，所以我们标记这个点的最短路径
     vis[x] = true;
     //遍历x的每一条边(x,j)并且更新d[j]
     for(int j = 0;j < n;j++)
        d[j] = min(d[j],d[x]+G[x][y]);
}

现在是优先队列的dijkstra：

先定义边：//这样的边是包含权值
struct edge{
     int from,to,weight;//出，入，边权
     edge(int u,int v,int w):from(u),to(v),weight(w){}
};

这里我使用vector模拟邻接表，之后的bellman_ford使用链式前向星：

struct dijkstra{
    int n,m;//点数和边数
    vector<int> G[N];//邻接表
    bool done[N];//记录是否找到了最短路径
    int d[N];//记录每个顶点到源点的距离
    //int p[N];
    
    void init(int x){//初始化
       n = x;
       for(int i = 0;i < n; i++)
       G[i].clear();
    }
  
    void add(int u,int v,int w){//加边
        G[u].push_back(edge(u,v,w));
    }
    struct node{
        int dist,id;//dist为点到源点的距离，id为点的标号
        node(int i,int d):dist(d),id(i){}
        bool opertor < (const int &a)const{
            return dist > a.dist;//距离越小的优先级越高
        }
    }；
    void dijkstra(int s){
        priority_queue que;//优先队列储存每一个结点
        que.push(node(s,0));//入队
        while(!que.empty()){
             node x = que.front();//取队头，即当前最短距离
             que.pop();
             if(done[x.id]) continue;//已经找到最短距离的不需要再找了
             done[x.id] = true;
             for(int i = 0;i < G[i].size();i++){
                   int v = G[u][i].to;//检查每一个邻居
                   if(done[v] > done[x.id]+G[u][i].weight){
                        //如果可以变小加入优先队列
                        d[v] = done[x.id]+G[u][i].weight;
                        que.push(node(v,d[v]));
                   }
             }
        }
    }
};

现在整个算法结束了。

4.BFS与dijkstra

我们发现dijkstra就是BFS加优先队列。
但事实真的就是如此吗？
如果优先队列里面的元素不是离源点最近的点，换成其他的元素会是什么呢？
prim算法就是其他元素的实现。

码农公寓