最短路径

floyd

是一种动态规划算法，稠密图效果最佳，边权可正可负

他的原理在于用邻接矩阵存任意两点之间的最短路径，适用于多源最短路，点与点之间：

1. 自己到自己——dis=0；
2. 自己到别人——找一mid，随机二分，就一区间DP

//k为中间点 
for(k = 0; k < G.vexnum; k++)
//v为起点 
    for(v = 0 ; v < G.vexnum; v++)
    //w为终点 
        for(w =0; w < G.vexnum; w++)
            if(D[v][w] > (D[v][k] + D[k][w]))
            {
                D[v][w] = D[v][k] + D[k][w];//更新最小路径 
                P[v][w] = P[v][k];//更新最小路径中间顶点 
             }

dijkstra算法

#include
#define MAXN 100010 
#define INF 2147483647
#define ll long long
using namespace std;
struct edge{ll w,v;};
ll n,i,j,beg,end,x,y,z,m;
vector g[MAXN];
edge E,E1;
ll dis[MAXN],vis[MAXN];
struct Node{
    ll w,v;
    bool operator < (const Node& x) const{
        return v>=x.v;
    }
};
priority_queue q;
Node node;
namespace Fastio{
    inline ll read(){ 
        ll x=0;char c=getchar();
        while(!isdigit(c)) c=getchar();
        while(isdigit(c)) {x=x*10+c-48;c=getchar();}
        return x;
    }
    void write(ll x){ 
        if(x/10>0) write(x/10);
        putchar(x%10+48);
        return;
    }
}
using namespace Fastio;
inline void Dijkstra(){
    while(!q.empty()){ 
        ll ww=q.top().w;q.pop();                   //取出队列首元素，队列放出元素
        if(vis[ww]) continue;                      //如果访问过此节点，直接continue
        vis[ww]=1;                                 //将该节点设置为走过
        for(i=0;i