图论-最短路

小鱼儿 2022-05-28 02:05 189阅读 0赞

单源最短路：

单元最短路问题是固定一个起点，求它到其他所有点的最短路的问题。终点固定的问题也叫单源最短路。

算法1：Bellman-Ford算法

记从起点s出发到顶点i的最短路为d\[i\],则:

d\[i\]=min(d\[i\],d\[j\]+G\[j\]\[i\])(G\[j\]\[i\]表示顶点j到i的距离)

初始化d\[s\]=0,其他均为inf,枚举每一条边，不断通过刚才的式子进行更新，更新数组d,就可以得到起点s到每一个顶点的最短路。

算法限制:必须保证图中不存在负圈.

算法原理:枚举每一条边，通过刚才的式子进行更新d，如果没有更新的值，则退出

时间复杂度:O(V\*E)

代码如下:

ps:如果图中不存在从s可达的负圈，那么同一个最短路不会经过同一个顶点俩次（也就是说，最多通过V-1条边),用此可以检查图是否带有负圈

代码如下:

bool find_negative_loop()
    {
        memset (d,0,sizeof (d));
        for (int i=0;i<V;i++) {
            for (int j=0;j<E;j++) {
                ege e=es[j];
                if (d[e.to]>d[e.from]+e.cost) {
                    d[e.to]=d[e.from]+e.cost;
                    if (i==V-1) return true;
                }
            }
        }
        return false;
    }

算法2：Dijkstra算法

在没有负边的情况下，在BEllman-Ford算法中，如果d\[j\]还不是最短距离时，那么即d\[i\]=min(d\[i\],d\[j\]+G\[j\]\[i\])(G\[j\]\[i\]表示顶点j到i的距离)，进行更新，d\[i\]也不会变成最短距离。而且d\[j\]没有变化是，每一次都要检查一遍，很浪费时间，对算法进行修改:

1:找到最短距离已经确定的顶点，从它出发更新相邻的顶点的最短距离

2:已经确定的最短距离的顶点不需要更改

算法限制:图中不允许有负边

时间复杂度:o(V\*V)

代码如下:

算法3：Dijlstra的优化

我们每一次都要枚举所有的顶点来查找下一个使用的顶点，因此很浪费时间，需要考虑新的数据结构来降低时间复杂度。

需要优化的数值更新和取最小值的情况，可以使用堆来优化，堆结构满足要求,把每个顶点当前的最短距离用维护，更新最短距离时，把对应元素往根方向移动，而取最小值就是堆顶，也可以使用STL中的priority\_queue来实现

算法限制:图中不允许有负边

时间复杂度:O(E\*log(V)）

代码如下:

typedef pair<int,int> P;//first 最短距离 second 顶点
    const inf=0x3f3f3f3f;
    const int maxn=1e3+100;
    struct ege{
        int from,to,cost//起点，终点，权值
    };
    vector<ege> G[maxn];
    int d[maxn];
    int V;
    
    void dijkstra(int s)
    {
        priority_queue<P,vector<P>,greater<p> > que;
        for (int i=0;i<V;i++) {
            d[i]=inf;
        }
        d[s]=0;
        que.push(P(0,s));
        while (que.size()) {
            P p=que.top();
            que.pop();
            int v=p.second;
            if (d[v]<p.first) continue;//没有最优解好，不必更新
            for (int i=0;i<G[v].size();i++) {
                ege e=G[v][i];
                if (d[e.to]>d[e.from]+e.cost) {
                    d[e.to]=d[e.from]+e.cost;
                    que.push(P(d[e.to],e.to));
                }
            }
            
        }
    }

任意俩点间的最短路

求解所有俩点间的最短路的问题叫做任意俩点间的最短路问题。

1：Floyd-Warshall算法

算法原理：非常简单，G\[i\]\[j\]表示顶点i到顶点j的最短距离，我们运用dp的思想，枚举其它的每一条边G\[i\]\[k\]与G\[k\]\[j\]来更新G\[i\[j\]

G\[i\]\[j\]=min(G\[i\]\[j\],G\[i\]\[k\]+G\[k\]\[j\])

不存在的边为inf

时间复杂度:O(V^3)

代码如下: