思路

题目分析

1. 该题是一个寻找图最短路径的问题
2. 题目给出两组节点，根据图内的节点关系求一组到另一组的最短路径，返回这个最短路径

方法一：Floyd算法（超时）

1. 多源最短路径算法
2. 不适用负权回路图

• 思路
  • Floyd的方法是通过三轮循环进行，可以求出任意两个节点之间的最短路径
  • 图要先转成邻接矩阵
  • 关键有三个循环
    • 第一层循环：选择某个结点作为中转结点 for(int k=1 to N)
    • 第二层循环：选择某个结点作为边起始点 for(int i=1 to N)
    • 第三层循环：选择某个结点作为边终止点 for(int j=1 to N)
  • 三层循环判断内容：比较是否经过该中转站后，两个节点之间的距离更近，通过不断地进行中转松弛操作确定最短路径
  • if(graph[i][j]>graph[i][k]+graph[k][j]) graph[i][j]=graph[i][k]+graph[k][j];

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param serialP intvector 牛牛占领的p个星球的编号
     * @param serialQ intvector 牛妹占领的q个星球的编号
     * @param path intvector<vector<>> m条隧道，每条隧道有三个数分别是ui,vi,wi。ui,vi分别是隧道的两边星球的编号，wi是它们之间的距离
     * @param nn int 星球个数n
     * @return int
     */
    int Length(vector<int>& serialP, vector<int>& serialQ, vector<vector<int> >& path, int nn) {
        // write code here
        int unReach = 1E5+1;
        vector<vector<int>> graph(nn + 1, vector<int>(nn + 1, unReach));	// 给出邻接矩阵
        for(auto e : path) {												// 将图转换成邻接矩阵
            int u = e[0], v = e[1], w = e[2];
            graph[u][v] = min(graph[u][v], w);
            graph[v][u] = min(graph[v][u], w);
        }
        for(int i = 1; i <= nn; i++) graph[i][i] = 0;						// 对节点本身到本身的情况单独赋值
        
      	// Floyd算法的三轮循环
        for(int k = 1; k <= nn; k++) {										
            for(int i = 1; i <= nn; i++) {	
                for(int j = 1; j <= nn; j++) {
                    if(graph[i][j] > graph[i][k] + graph[k][j]) 			// 松弛操作
                        graph[i][j]=graph[i][k]+graph[k][j];
                }
            }
        }
        
        //最后来发现最短dis
        int dis = INT_MAX;
        for(int bro : serialP) {
            for (int sis : serialQ) {
                dis = min(dis, graph[bro][sis]);
            }
        }
        return dis >= unReach ? -1 : dis;
    }
};

复杂度分析

• 时间复杂度：$O(N^3)O(N^3)$，使用了三轮循环，代价很高
• 空间复杂度：$O(N^2)O(N^2)$，使用邻接矩阵来存储最短路径

方法二：SPFA算法

1. 允许负权边的存在——改善Dijkstra不可以有负权边的特点
2. 不允许负权环路的存在（但可以判断是否 return -1）

• 思路
  • 我们引入一个超级节点，作为一组（牛妹）的所有节点的起点，设置其到牛妹的所有节点距离为0
  • 将图 $GG$ 制成邻接表的形式进行访问，加快访问速度
  • 维护 d[] 数组，作为最短路径存储数组，在算法过程中不断更新，初始化起点为0，其他的点都是max
  • 采用动态逼近的思想
    • 维护一个先进先出的队列用来保存待优化的结点
    • 优化时，每次取出首节点$uu$，并对所有的 $(u,v)(u,v)$ 进行松弛操作。
      • 如果 $vv$ 不在队列中 且 $vv$ 的状态有更新，就将 $vv$ 放入队尾
    • 直到队空为止

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param serialP intvector 牛牛占领的p个星球的编号
     * @param serialQ intvector 牛妹占领的q个星球的编号
     * @param path intvector<vector<>> m条隧道，每条隧道有三个数分别是ui,vi,wi。ui,vi分别是隧道的两边星球的编号，wi是它们之间的距离
     * @param nn int 星球个数n
     * @return int
     */

    
    int Length(vector<int>& serialP, vector<int>& serialQ, vector<vector<int> >& path, int nn) {
        // write code here
        vector<vector<pair<int, int>>> graph(nn + 1);        // 图的邻接表
        int longest = 1e5+1;                                 // 不可达长度
        vector<int> d(nn + 1, longest);                      // 出发点到各个点的最小路径
        d[0] = 0;                                            // 出发点初始化
        vector<bool> exist(nn + 1, false);                   // 检查队列中是否存在
        
        // 将图转化为邻接表形式
        for(auto e : path) {
            int u = e[0], v = e[1], w = e[2];
            graph[u].emplace_back(v, w);
            graph[v].emplace_back(u, w);
        }
        
        // 加入超级初始节点
        for(int v : serialQ){
            graph[0].emplace_back(v, 0);
        }
        
        // 维护队列
        queue<int> q;
        q.push(0);
        exist[0] = true;
        while(!q.empty()) {
            int u = q.front();                        // 从队首取出节点
            q.pop();
            exist[u] = false;                         // 标记节点不存在队列钟
            
            for(auto [v, w] : graph[u]) {             // 分析u节点相连的所有v节点，对u-v路径进行松弛操作
                if(d[v] > d[u] + w) {                 // 松弛
                    d[v] = d[u] + w;
                    if(!exist[v]) {                   // 检查是否要重新入队
                        q.push(v);
                        exist[v] = true;
                    }
                }
            }
        }
        
        int ret = longest;
        for(int u : serialP) ret = min(ret, d[u]);    // 筛选最小值
        return ret >= longest ? -1 : ret;
    }
};

复杂度分析

• 时间复杂度：最坏的时间复杂度 $O(\mathrm{\mid }V\mathrm{\mid }\mathrm{\mid }E\mathrm{\mid })O(|V||E|)$ ， 其中 $\mathrm{\mid }V\mathrm{\mid }|V|$ 为所有顶点数量，$\mathrm{\mid }E\mathrm{\mid }|E|$为所有边的数量 。
• 空间复杂度：$O(N^2)O(N^2)$，使用邻接表来存储边的关系