模闆整理: 圖論---最短路

最短路……基礎但重要……

主要有floyd，dijkstra，SPFA這種，

看資料範圍的。

floyd還可以用來求傳遞閉包，也就是連通性的問題。

最短路問題：給出一張圖，求s~t的最短路。

1.floyd算法。

使用它的時候一般都是用鄰接矩陣計算了……

//dis[i][j]一開始的初值：
//若輸入的邊裡有(i,j)，則dis[i][j]為其權值
//不然dis[i][j]=INF
for (int k=1;k<=n;k++)
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);      

……注意了有個問題就是如果初始化的值過大，

然後dis[i][k]和dis[k][j]都為INF，

INF過大……兩個相加……就會爆辣！

是以初值要麼不要太大，要麼更新的時候判斷一下。

2.dijkstra算法+堆優化

……最穩的最短路算法了。

優化一下找最小dis的過程，用堆維護，

C++STL輕松= v =

如果堆加上映射，也就是增加删除操作會更快。

多用用它吧！

//head,E都是邊表（連結清單）的部分……
//stl大法好（可憐P黨QAQ）
struct Heap{int num,val;};
priority_queue<Heap,vector<Heap> >Q;
bool operator <(Heap x,Heap y){return x.val>y.val;}
bool operator >(Heap x,Heap y){return x.val<y.val;}

void dijkstra(int s,int t){
    memset(vis,0,sizeof(vis));
    memset(dist,100,sizeof(dist));
    dist[s]=0;
    Q.push((Heap){s,0});
    while ((!Q.empty())){
        Heap mi=Q.top();Q.pop();
        if (vis[mi.num]) continue;
        vis[mi.num]=1;
        for (int j=head[mi.num];j;j=E[j].next){
            int q=E[j].to;
            if (vis[q]) continue;
            if      

//這裡用了循環隊列，循環長度是M
int SPFA(int sta,int end){
    memset(vis,0,sizeof(vis));
    memset(dis,60,sizeof(dis));
    int h=0,tail=1;
    Q[0]=sta; dis[sta]=0;
    while (h!=tail){
        int u=Q[h];
        h=(h+1)%M;
        vis[u]=0;
        for (int i=head[u];i;i=E[i].next)
            if (dis[u]+E[i].val<dis[E[i].to]){
                dis[E[i].to]=dis[u]+E[i].val;
                if (!vis[E[i].to]){
                    vis[E[i].to]=1; 
                    Q[tail]=E[i].to;
                    tail=(tail+1)%M;
                }
            }
    }
    return