大本赢彩票开户

码迷,xscp18.com
大本赢彩票开户 > 其他好文 > 详细

图论复习

时间:2019-09-01 01:49:48      阅读:46      评论:0      收藏:0      [点我收藏+]

标签:时间   优先   长度   oid   pre   复杂   代码   dijkstra   空间复杂度   

图论复习

最短路

多源最短路

算法:Floyd

其实本质上是一种dp

f[i][j][k]表示i到j允许通过前k个点的最短路径长度

一开始所有点都无法作为中转点,然后逐步允许放开每个点最为中准点

大本赢彩票开户每步的转移有两种决策:是/否通过第k个点

由于k是递增的,且当k一定时,f[i][k][k]和f[k][j][k]的值都是不变的,故我们只需要用一个二维数组f[i][j]表示i到j的最短路长度即可,可以节省很多空间。

for(int k = 1; k <= n; k++)
{
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            f[i][j] = min(f[i][k], f[i][k] + f[k][j]);
        }
    }
}

时间复杂度:O(n3) 空间复杂度:O(n2) 边的储存方法:邻接矩阵

优点:1.求多源最短路的”唯一“算法 2.代码简单易写 缺点:适用范围较窄

注意事项:由于邻接矩阵存边无法处理重边,在存边时要注意判重边(取min/max)。

单源最短路

算法:dijkstra/spfa

dijkstra

本质是贪心 前提:边权全部为正

大本赢彩票开户每次找到未被更新的距离起点最近的点,并用该点更新剩余的点。

正确性证明:每个点如果能被更新,它一定是被比它更近的点更新,如果比它更近的点已经被更新完了,它将不再被更新。

优化:每次寻找最近的点会花费大量的时间,因此我们选择采用优先队列来存dis值,每次只需弹出队列顶部,看它是否被更新过即可。

struct node
{
    int x, d;
    bool operator < (const node &b) const {return d > b.d;}
};
priority_queue<node> q;
void dijkstra(int s)
{
    q.push((node){s,0});
    while(!q.empty())
    {
        node A=q.top();q.pop();
        int u = A.x;
        if(vis[u] == 1)continue;
        vis[u] = 1;
        for(int i = fir[u]; i; i = nxt[i])
        {
            int v = vv[i];
            if(v == fa)continue;
            if(dis[v] > dis[u] + edge[i])
            {
                dis[v] = dis[u] + edge[i];
                q.push((node){v, dis[v]});
            }
        }
    }
}

朴素做法时间复杂度:O(n2)

堆优化时间复杂度:O(m logm) 每次把边存入优先队列的时间复杂度的为O(logm)

图论复习

标签:时间   优先   长度   oid   pre   复杂   代码   dijkstra   空间复杂度   

原文地址:https://www.cnblogs.com/Akaina/p/11440965.html

(0)
(0)
   
举报
评论 一句话评论(0
登录后才能评论!
           
© 2014 xscp18.com 版权所有 京ICP备13008772号-2
迷上了代码!
亿家彩票开户 鼎顺彩票开户 爱乐彩票开户 爱嬴彩票开户 爱乐透彩票开户 盛兴彩票开户 新贝彩票开户 博宏彩票开户 天天彩票开户 金丰彩票开户