Dijskra & Floyd & bellman Ford

快来打我* 2023-01-22 10:58 30阅读 0赞

**可供测试的样题**

[牛客链接][Link 1]

**注意这个题目里面的边是会重复出现的，我们只保留所有重边中最小的那个**

**Dijstra**

class Solution { 
    public:
        
        int findShortestPath(int n, int m, vector<vector<int> >& gr) { 
            
            vector< vector<int>> g(n+1,vector<int>(n+1,INT_MAX/3));
            for(auto& v:gr){ 
                g[ v[0] ][ v[1] ] = min(g[ v[0] ][ v[1] ],v[2]);
            }
            
            vector<int> dis(n+1,INT_MAX);
            vector<bool> isin(n+1,false);
    
            int kn=1;
            dis[1] = 0;
            int lastin = 1;
            isin[1] = true;
            while(kn < n){ 
               for(int i=1;i<=n;++i){ 
                   dis[i] = min(dis[i],dis[lastin] + g[lastin][i]); 
               }
                
               lastin=-1;
               for(int i=1;i<=n;++i){ 
                   if( !isin[i] ){ 
                       if( lastin==-1 ){ 
                           lastin = i;
                       }
                       else if( dis[lastin] > dis[i] ){ 
                           lastin = i;    
                       }
                   }
               }
               isin[lastin] = true;
               kn++;
            }
            return dis[n]==INT_MAX/3?-1:dis[n];
        }
    };

![在这里插入图片描述][20210519164102492.png]

--------------------

**Floyd**

class Solution { 
    public:
        
        int findShortestPath(int n, int m, vector<vector<int> >& graph) { 
            vector< vector<int> >g(n,vector<int>(n,INT_MAX/3));
            
            for(auto c:graph){ 
                g[ c[0]-1 ][c[1]-1] = min(c[2],g[ c[0]-1 ][c[1]-1]);
            }
            
            for(int k=0;k<n;++k){ 
                for(int i=0;i<n;++i){ 
                    for(int j=0;j<n;++j){ 
                        g[i][j] = min(g[i][j],g[i][k] + g[k][j]);
                    }
                }
            }
            return g[0][n-1]==INT_MAX/3?-1:g[0][n-1];
        }
    };

![在这里插入图片描述][20210519163955476.png]

[Link 1]: https://www.nowcoder.com/practice/9f15b34a2a944a7798a5340ff0dba8b7?tpId=196&tqId=37573&rp=1&ru=/activity/oj&qru=/ta/job-code-total/question-ranking&tab=answerKey
[20210519164102492.png]: /images/20221020/0d3ae94494a2483e895de9463824ecdd.png
[20210519163955476.png]: /images/20221020/5b9987505fa549f19ff33566cde37f23.png