【図論アルゴリズム】最短,二次短絡,k短絡まとめ

図論では,最短,二次短絡,k短絡の問題がよく見られる.ここでまとめます.
グラフィックテクニック
データが小さく、稠密図の一般用隣接行列疎図、データが大きい一般用隣接表(vector、チェーン式前方星都可)
隣接行列

const int maxn = 1e5+5;
int Graph[maxn][maxn];	//          -1       ，                     。

チェーンフォワードスター

const int maxn = 1e5+5;
struct Edge{
		int u,v,nxt;
}edge[maxn];
int head[maxn],tot;
inline void addedge(int u,int v,int w){	// u->v    w
		edge[++tot] = {u,v,w};
		head[u] = tot;
}

さいたんらく
一般的な最短アルゴリズムにはBFS(暴力、一般的に点数が小さい場合のみ適用)、dijiastra(正権図を解決)、spfa(負権図を解決するが、死にやすく、カードされる)、floyed(点と点の間の最短距離問題を解決し、dp)がある.
ここでは,単一ソースの最短回路のアルゴリズム(よく理解されているため)を直接与える(操作の緩和に重点を置く!)
dijiastra

//      
const int maxn = 1e5+5;
struct Edge{
    int u,v,nxt,w;
}edge[maxn];
int head[maxn],tot;
inline void init(){
    memset(head,-1,sizeof(head));
}
inline void addedge(int u,int v,int w){
    edge[++tot] = {u,v,head[u],w};
    head[u] = tot;
}
int dis[maxn];  bool vis[maxn];
inline void dijiastra(int s){
    struct Node{
        int u,dis;
        bool operator <(const Node &h)const{
            return dis > h.dis;
        }
    };
    memset(dis,0x3f,sizeof(dis));   //              
    dis[s] = 0;
    priority_queue<Node> pq;    pq.push(Node{s,0});
    while(!pq.empty()){
        Node u = pq.top();  pq.pop();
        if(vis[u.u])    continue;
        vis[u.u] = true;
        for(int i = head[u.u]; ~i; i = edge[i].nxt){
            Edge &e = edge[i];
            if(dis[e.v] > u.dis + e.w){
                dis[e.v] = u.dis + e.w;
                pq.push(Node{e.v,dis[e.v]});
            }
        }
    }
}

spfa

struct Edge{
    int v,d;
    Edge(int vv,int dd):v(vv),d(dd){}
};
struct Node{
    int u,cost;
    Node(int uu,int cc):u(uu),cost(cc){}
    bool operator < (const Node & h)const{
        return cost > h.cost;
    }
};
const int MAX = 1e5+5;
vector < Edge > edges;
vector < int > Graph[MAX];
bool vis[MAX];
int dp[MAX];
void AddEdge(int u,int v,int dis){
    edges.push_back(Edge{v,dis});
    Graph[u].push_back(edges.size()-1);
}
void SPFA(int s,int n){
    memset(dp,0x3f,sizeof(dp));
    dp[s-1] = 0;
    priority_queue<Node>q ;
    q.push(Node{s-1,0});  vis[s-1] = 1;
    while(!q.empty()){
        Node x = q.top(); q.pop();
        int u = x.u; vis[u] = 0; // cancel the tag;
        for(int i = 0; i < Graph[u].size(); ++i ){
            Edge & e = edges[Graph[u][i]];
            if( dp[e.v] > dp[u]+ e.d ){
                dp[e.v] = dp[u] + e.d;
                if(!vis[e.v]) q.push(Node{e.v,dp[e.v]});
                  vis[e.v] = 1;
            }
        }
    }
}

セカンダリショート
現在見られている方法は一般的に2種類あり,遍歴or削除エッジ
1.エッジを削除します.まず最短アルゴリズムを用いてs−t s−t s−t−s−tの最短経路を求め,最短経路(緩和時に前駆者を記録)を記録した後,この経路について順次エッジを削除し,その後最短経路を走りansを更新する

#include
using namespace std;
const int maxn = 1e5+5;
const double inf = 1e9+5;
struct Edge{
    int u,v,nxt;    double w;
}edge[maxn];
int head[maxn],tot;
pair<int,int> path[maxn];
inline void addedge(int u,int v,double w){
    edge[++tot] = {u,v,head[u],w};
    head[u] = tot;
}
inline void init(){
    memset(head,-1,sizeof(head));
    tot = 0;
}

double dis[maxn];   bool vis[maxn];
bool isok[maxn];
inline void dijiastra(int s){
    struct Node{
        int u;  double dis;
        bool operator <(const Node &h)const{
            return dis > h.dis;
        }
    };
    for(int i = 0; i < maxn; ++i)  dis[i] = inf,vis[i] = false;
    priority_queue<Node> pq;    pq.push(Node{s,0});
    while(!pq.empty()){
        Node u = pq.top();  pq.pop();
        if(vis[u.u])
            continue;
        vis[u.u] = true;
        for(int i = head[u.u]; ~i; i = edge[i].nxt){
            if(isok[i]) continue;
            Edge &e = edge[i];
            if(dis[e.v] > u.dis + e.w){ //         
                dis[e.v] = u.dis + e.w;
                path[e.v] = make_pair(u.u,i);
                pq.push(Node{e.v,dis[e.v]});
            }
        }
    }
}
struct Point{
    int x,y;
}p[maxn];
inline double get_dis(const Point &p,const Point&q){
    return sqrt( (p.x-q.x)*(p.x-q.x) + (p.y-q.y)*(p.y-q.y));
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    init();
    int n,m;    cin >> n >> m;
    for(int i = 1; i <= n; ++i) cin >> p[i].x >> p[i].y;
    for(int i = 0,u,v; i < m; ++i){
        cin >> u >> v;  double d = get_dis(p[u],p[v]);
        addedge(u,v,d); addedge(v,u,d);
    }
    dijiastra(1);
    pair<int,int> tt = path[n];
    vector<int> ee; ee.push_back(tt.second);
    while(tt.first!=1){
        tt = path[tt.first];
        ee.push_back(tt.second);
    }

    double ans = inf;
    for(int i = 0; i < ee.size(); ++i){
        isok[ee[i]] = true;
        dijiastra(1);
        isok[ee[i]] = false;
        ans = min(ans,dis[n]);
    }
    if(ans==inf){
        cout << -1 << endl;
    }
    else cout <<fixed<<setprecision(2)<< ans << endl;
    return 0;
}

2.遍歴.最短ルートを2回走って、それぞれ起点で、終点で.次に、すべてのエッジを巡回し、長さΣe(u,v)∈G(v,e)m i n(d i s[1][u]+w(u,v)+d i s[v][n])を更新します.{e(u,v)\in G(v,e)}min(dis[1][u]+w(u,v)+dis[v][n]) ∑e(u,v)∈G(v,e)​min(dis[1][u]+w(u,v)+dis[v][n])
k短絡(A*または左偏樹)(もちろん二次短絡問題の解決にも用いられる)
左偏樹、A*更新待ち
左偏樹学習:大物ブログ