在标记邻居的最短路径后查找图中所有剩余的顶点

---

关于图搜索算法的算法遍历图以寻求广泛的发现或目标搜索。这些算法在网络中切割路径，但没有人期望这些路径在计算上是最优的。寻路算法也构建在图搜索技术之上，因为它们探索顶点之间的路径，从特定节点开始，并通过连接直到访问目标。

什么是图？

图是反映一组组件之间“连接”的数据结构。

这些项目称为节点。边是节点之间的连接。

最短路径

最短路径算法找到任意两个节点或顶点之间最短的路径或权重最小的边。因为它实时运行，所以非常适合用户交互和动态工作流程。

算法类型	功能	使用示例
最短路径变体	找到两个顶点之间的最短路径。	获取跨不同点的驾车路线
"单源最短路径"	找到根节点与所有其他节点之间的最短路径。	最便宜的呼叫路线
"所有节点对最短路径"	找到图中任意两个节点之间的最短路径。	考虑其他路径以避免交通拥堵。

迪杰斯特拉算法

迪杰斯特拉算法构建一组从源到目标距离最小的节点，以从单个源节点获得“最短路径树”。

迪杰斯特拉算法的基本原理是什么？

迪杰斯特拉算法的基本原理如下所示：

• 迪杰斯特拉算法从您指定的节点（也称为起始节点）开始，然后继续分析图以发现连接该顶点和图中所有其他节点的最短路径。

• 此技术跟踪源节点和每个节点之间的最短距离，并在找到更短的路径时更改值。

• 一旦找到连接源和另一个节点的最小距离，该顶点就会被标记为“已访问”并添加到路径中。

• 重复此过程，直到图中的所有顶点都包含在路径中。因此，建立了通过到每个节点的最短可行路径将主节点连接到每个节点的路径。

注意

图分析在描述链接和路径时会使用术语，例如：

• "权重" - 关系特定特征的数值实体。

• "成本" - 在评估路径的总权重时，我们会经常遇到它。

• "距离" 是连接属性的常用名称，它反映了在算法中两个节点之间行进的距离。

• "跳数" 指两个顶点之间的连接数。

迪杰斯特拉算法的主要用途

此方法在 GPS 设备中确定当前位置和目标位置之间的最短路径。它在行业中有多种用途，主要是在需要网络建模的领域。

如果图的边具有负权重，迪杰斯特拉算法是否可以工作？

答案是否定的。

迪杰斯特拉算法只能用于具有正权重的图。这是因为必须添加边的权重才能检测最短路径。

对于具有负权重的图，该算法将无法正常工作。当一个节点被标记为“已访问”时，通向该节点的当前路径成为最短路径。负权重可能会改变这一点，因为总权重将在此阶段之后减少。

在完成标记图中邻居的最短路径以识别所有剩余顶点后该怎么办？

该过程是遍历每个顶点并用最低列号的节点标记该节点，通过权重最小的边连接到主顶点。然后找到连接到当前节点的权重最小的边，然后找到每个未标记的边。

要克服此问题，请按照以下步骤操作

使用两个循环 j 和 i 遍历整个邻接矩阵。

对于每个（行），找到邻接矩阵中的最小结果；列号最小的节点通过权重最小的边连接到主顶点。

使用布尔数组，为每个顶点标记此顶点。

打印布尔数组中未标记的每个顶点或节点。

此方法的实现如下

示例

#include <iostream>
#include <string>
#include <vector>
#include <limits>
 
// Stdc++11 code to implement the approach
class GFG{
   
   // Function to calculate the number of unmarked edges
   public:
   static std::vector<bool> markedNodesCounter(std::vector<std::vector<int>> &A, int V){
       
      // Initialising visited array
      std::vector<bool> marked(V);
       
      // Loop to iterate through every node
      for (int i = 0; i < V; i++){
           
         // Initialising the minimum distance and the node closest to the current node
         int minweight = std::numeric_limits<int>::max();
         int min = V + 1;
           
         // loop to find the weights from current node to every other node
         for (int j = 0; j < V; j++){
            if (i == j){
               continue;
            }
            if (A[i][j] < minweight){
               minweight = A[i][j];
               min = j;
            }
         }
         // Marking the closest node
         marked[min] = true;
      }
      // Returning the answer
      return marked;
   }
   // Driver Code
   static void main(std::vector<std::string> &args){
      int V = 3;
      std::vector<std::vector<int>> A{{0, 10, 50}, {10, 0, 30}, {50, 30, 0}};
      // Getting the result
      std::vector<bool> marked = GFG::markedNodesCounter(A, V);
      // Printing the result
      bool flag = false;
      for (int i = 0; i < V; i++){
         if (!marked[i]){
            std::cout << std::to_string(i) + " ";
            flag = true;
         }
      }
      if (!flag){
         std::cout << "-1" << std::endl;
      }else{
         std::cout << std::endl;
      }
   }
};
int main(int argc, char **argv){
   std::vector<std::string> parameter(argv + 1, argv + argc);
   GFG::main(parameter);
   return 0;
};

输出

根据以上代码：

2

辅助空间为 O(V)，时间复杂度为 O(V2)，用于生成一个大小为 V 的额外数组，并初始化两个分别从 0 到 V 的嵌套循环。

哪些情况需要最短路径？

使用最短路径算法，您可以根据跳数或任何其他加权连接值确定两个节点之间的最佳路径。它可以提供有关分离程度、两个位置之间的最小路径或最便宜路径的即时响应。还可以使用此方法来调查特定节点之间的关系。

结论

寻路算法可以帮助我们理解数据之间的关系。迪杰斯特拉算法发现网络中两个节点之间的最短路径。此方法使用边权重来检测将主顶点连接到所有顶点的总权重最小的路径。