對圖論和搜索的學習感想

Dijkstra

迪杰斯特拉求最短路的暴力的思路是三重回圈去更新所有點到起點的最短距離，

首先先初始化讓第一個點到自己的距離是0即：

dist[1]=0;

然后在省下的點中找到距離起點最近的點（該點必須是沒有被確定的點），然后再用該點到起點的距離更新所有點到起點的最短距離，每次更新一個最短，最短更新全部，所以第一重回圈回圈n次，從而達到尋找最短路的效果，

for(int i=0;i<n;i++)
    {
        //找出距離原點最短的點
        int t=-1;
        for(int j=1;j<=n;j++)
        {
            if(!str[j]&&(t==-1||dist[t]>dist[j]))t=j;
        }
        //加入集合
        str[t]=true;
        //更新距離
        for(int j=1;j<=n;j++)
        {
            dist[j]=min(dist[j],dist[t]+g[t][j]);
        }
    }

但是不是回圈太多次了？如果遇到大的資料，時間肯定會超時，那么應該怎么辦呢，其實迪杰斯特拉演算法是可以用堆優化的，具體可以用到priority_queue優先佇列去優化,為什么呢，首先我們在我們優化前，我們找到最短邊，然后跟新所有點，這個時候會發生什么呢，有些點不一定會被更新，這樣子我們效率就會比較低，當資料很大的時候，很容易爆掉，那么有什么是可以全面檢索并且可以保證檢索一次呢？這不是和寬搜很類似嗎，所以我們可以用寬搜進行優化，當你更新成功時你才入隊

 while(!pq.empty())
    {
        auto t=pq.top();
        pq.pop();
        
        int var = t.second, distance=t.first;
        
        if(str[var])continue;//如果已經更新過了就直接跳過，否則就開始更新，然后該點加入已更新的集合
        str[var]=true;
        
        
        for(int i=h[var];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>distance+w[i])//如果你成功更新，則入隊
            {
                dist[j]=distance+w[i];
                pq.push({dist[j],j});
            }
        }
        
    }

這樣的時間復雜度就是o（nlogm）的，

bellman-ford和spfa

bellman-ford和spfa一般是用于可能存在負權邊的時候（spfa還可以用于判斷負環），bellman演算法比較方便，那些點不需要什么特殊的方式去存，只要能存就可以了，仔細想想真的暴力，bellman演算法的時間復雜度是o（nm）的然后他是遍歷所有邊和一步一步更新最后達到最優解，

struct{
    int p,o,l;
}e[N];
int dist[N],baccom[N];
int bellman()//這是用bellman-ford演算法做有邊數限制的最短路
{
    memset(dist,1000000,sizeof(dist));
    dist[1]=0;
    for(int i=0;i<k;i++)
    {
        memcpy(baccom,dist,sizeof(dist));
        for(int j=0;j<m;j++)//表示遍歷m條邊
        {
            int a=e[j].p,b=e[j].o,c=e[j].l;
            dist[b]=min(dist[b],baccom[a]+c);
        }
        
    }
    if(dist[n]>1000000/2)return -1;
    return dist[n];
}

那么為什么需要一個dist陣列還要一個baccom陣列呢，因為如果只用一個dist陣列去更新的話，有可能讓更新的點去更新別的點從而發生串聯，這是我們不希望看到的，就是在一次迭代中，可能發生a->b更新完之后，立馬又被拿來更新c了，這樣可能會導致到終點的邊的個數無法被限制，這是我們不想看到的，所以我們定義一個新的陣列，每次更新都用這個新的陣列去更新，保證每一次更新都是用的上一次更新好的值，從而避免串聯，當然，如果只是單純的做最短路不考慮串聯也是可以的，

spfa演算法，可以說是bellman的優化，最好的情況是o（n），最壞也是和bellman一致：

void add(int a,int b,int c)//鄰接表存圖
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int spfa()
{
    memset(dist,0x3f,sizeof(dist));
    queue<int> q;
    q.push(1);
    dist[1]=0;
    stl[1]=true;
     while(!q.empty())
    {
        int cur=q.front();
        q.pop();
        stl[cur]=false;

        for(int i=h[cur];i!=-1;i=ne[i])
        {
            int j = e[i];
            if(dist[j]>dist[cur]+w[i])
            {

                dist[j]=dist[cur]+w[i];
                if(!stl[j])
                {
                    stl[j]=true;
                    q.push(j);
                }

            }
        }
    }
    
    if(dist[n]==0x3f3f3f3f)return -1;
    else return dist[n];
}

bellman演算法是不管三七二十一我全部更新一遍，所以我們可以用寬搜的思路去優化———如果你更新成功，那么我才拿更新成功的距離去更新所有的點，stl這個bool陣列是為了防止我們寬搜的時候佇列里面存了重復的點，因為我們是拿佇列里面的點去更新所有的點的（換句話說，如果除佇列以外的點如果也能更新成功，那么就讓該點也入隊，去更新其他的點，所以我們才要防止重復的點進入佇列），最短路的話根據抽屜原理，另設一個cnt陣列去存點的邊的個數就好了，

Floyd

這個方法是o（n^3）的有點像是dp里面的記憶化，可以有效解決多源的最短路問題，

void floyd()
{
    for(int k=1;k<=n;k++)\
     for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
       d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
     
}

狀態表示：從i這個點，到j這個點的最短距離，

以上來自我對于acwing中演算法的學習見解，www.acwing.com