图论——最短路——基础

1   本质
    已知到点与点之间的相对路程
    求特定节点与特定节点的绝对路程dist
    比较a到b和a到c再到b的路程


2   存储
        节点编号一般是1~n
        有向/无向图/重边/自环
            无向*2

        稀疏图——邻接表    空间 m+n

            memset(h,0,sizeof h);   
            加入有向边(x,y) 权值为z
            void add(int x,int y,int z)
            {
                idx++;
                e[idx]=y;
                w[idx]=z;
                ne[idx]=h[x];
                h[x]=idx;
            }

            访问从x出发的所有边
            for(int i=h[x],i,i=ne[i])
            {
                int y=e[i];
                int z=w[i];
            }

       稠密图——邻接矩阵  空间 n^2
          反向存图可实现多对一
                = 0    ( a == b )
        g[a][b] = min( g[a][b] , c )
                = INF

3   类型

    多源    Floyd       O( n^3 )

    单源    边权为1     BFS

            边权为0或1  deque + BFS

            边权为正    朴素dijstra   稠密图  O( n^2 )
                       优化dijstra   稀疏图  O( mlogn )

            存在负权    SPFA    O( nm )

    经过不超过k条边     bellman-ford    O( nm )

4    负权边
        若有负权边是否能到达n号点的判断中需要
        进行if(dist[n] > INF/2)判断，而并非是if(dist[n] == INF)
        原因是INF是一个确定的值，并非真正的无穷大，
        会随着其他数值而受到影响，dist[n]大于某个与INF相同数量级的数即可