迹忆客 专注技术分享

当找到两个图节点之间的最短路径时，我们可以实现 Dijkstra 算法，这是一种广泛使用的算法。本教程描述了 Dijkstra 算法的过程，并演示了如何在 Java 中实现它。

Dijkstra 算法

Dijkstra 算法可以找到从源节点到加权图中所有节点的最短路径。最短路径也可以在图中的源顶点中找到。

通过 Dijkstra 算法找到最短路径将生成具有根源顶点的最短路径树 (SPT)。

在 Java 中实现 Dijkstra 算法时，我们维护两个列表或集合。第一个包含最短路径树中的所有顶点，第二个包含评估阶段的顶点以包含在 SPT 中。

我们在每次迭代中从第二个列表中找到一个顶点，它将具有最短路径。下面是 Dijkstra 算法的分步过程：

• 首先，将图中的所有节点标记为未访问。
• 现在，用零初始化起始节点；所有其他无穷大的节点表示最大的数字。
• 使起始节点成为当前节点。
• 这个当前节点现在将用于分析其所有未访问的邻居节点，然后通过添加边的权重来计算距离，这将建立当前节点和邻居节点之间的连接。
• 比较最近计算的距离和分配给邻居节点的距离；这将被视为相邻节点的当前距离。
• 现在，考虑当前节点周围尚未访问的节点，并将当前节点标记为已访问。
• 重复这个过程，直到结束节点被标记为已访问，这意味着 Dijkstra 的算法已经完成了它的任务。如果结束节点还没有被标记为已访问，那么：
• 选择路径最短的未访问节点，它将成为新的当前节点。然后从步骤 4 开始重复该过程。

Dijkstra 算法的伪代码

Method DIJKSTRA(G, SV)
    G-> graph;
    SV->starting vertex;
begin
    for every vertex VX in G    //initialization; set the initial path to infinite and current node to 0 or null;
        Distance[VX] <- infinite
        Current[VX] <- NULL
        If V != SV, add VX to Priority Queue    // During the first run, this vertex is the source or starting node
    Distance[SV] <- 0

    while Priority Queue IS NOT EMPTY    // where the neighbor ux has not been extracted  yet from the priority queue
        UX <- Extract MIN Neighbor from Priority Queue
        for each unvisited adjacent_node  VX of UX
            Temporary_Distance <- Distance[UX] + Edge_Weight(UX, VX)
            if Temporary_Distance < Distance[VX]    // A distance with lesser weight (shorter path) from ux is found
                Distance[VX] <- Temporary_Distance
                Current[VX] <- UX    // update the distance of UX
    return Distance[], Current[]
end

在 Java 中使用优先级队列实现 Dijkstra 算法

下面是使用优先级队列的 Dijkstra 算法的 Java 实现：

package delftstack;

import java.util.*;

public class Dijkstra_Algorithm {
  public static void main(String arg[]) {
    int Vertex = 6;
    int source_vertex = 0;
    // representation of graph will be the adjacency list
    List<List<Node> > Node_list = new ArrayList<List<Node> >();
    // For every node in the graph Initialize adjacency list
    for (int i = 0; i < Vertex; i++) {
      List<Node> item = new ArrayList<Node>();
      Node_list.add(item);
    }

    // The edges of the graph
    Node_list.get(0).add(new Node(1, 5));
    Node_list.get(0).add(new Node(4, 2));
    Node_list.get(0).add(new Node(2, 3));
    Node_list.get(1).add(new Node(5, 2));
    Node_list.get(1).add(new Node(4, 3));
    Node_list.get(2).add(new Node(3, 3));
    Node_list.get(2).add(new Node(4, 2));

    // Run the Dijkstra_Algorithm on the graph
    Graph_priority_queue gpq = new Graph_priority_queue(Vertex);
    gpq.Dijkstra_Algo(Node_list, source_vertex);

    // Printing the shortest path from source node to all other the nodes
    System.out.println("The shortest paths from source nodes to all other nodes:");
    System.out.println("Source_Node\t\t"
        + "Other_Node#\t\t"
        + "Path_Distance");
    for (int x = 0; x < gpq.distance.length; x++)
      System.out.println(source_vertex + " \t\t\t " + x + " \t\t\t " + gpq.distance[x]);
  }
}

class Graph_priority_queue {
  int distance[];
  Set<Integer> visited_Node;
  PriorityQueue<Node> Priority_Queue;
  int Vertex; // vertices
  List<List<Node> > node_list;
  // constructor
  public Graph_priority_queue(int Vertex) {
    this.Vertex = Vertex;
    distance = new int[Vertex];
    visited_Node = new HashSet<Integer>();
    Priority_Queue = new PriorityQueue<Node>(Vertex, new Node());
  }

  // Dijkstra's Algorithm implementation
  public void Dijkstra_Algo(List<List<Node> > node_list, int source_vertex) {
    this.node_list = node_list;

    for (int x = 0; x < Vertex; x++) {
      distance[x] = Integer.MAX_VALUE;
    }
    // add the source vertex to the Priority Queue
    Priority_Queue.add(new Node(source_vertex, 0));

    // Distance of the source from source itself is 0
    distance[source_vertex] = 0;
    while (visited_Node.size() != Vertex) {
      // ux is deleted from the Priority Queue which has minimum distance
      int ux = Priority_Queue.remove().dj_node;

      // add the ux node to finalized list which is visited
      visited_Node.add(ux);
      Adjacent_Nodes_Graph(ux);
    }
  }
  // process all the neighbors of the just visited node
  private void Adjacent_Nodes_Graph(int ux) {
    int Edge_Distance = -1;
    int New_Distance = -1;

    // process all neighboring nodes of ux
    for (int x = 0; x < node_list.get(ux).size(); x++) {
      Node vx = node_list.get(ux).get(x);

      //  if current node is not in 'visited'
      if (!visited_Node.contains(vx.dj_node)) {
        Edge_Distance = vx.dj_cost;
        New_Distance = distance[ux] + Edge_Distance;

        // compare the distances
        if (New_Distance < distance[vx.dj_node])
          distance[vx.dj_node] = New_Distance;

        // Add the current vertex to the PriorityQueue
        Priority_Queue.add(new Node(vx.dj_node, distance[vx.dj_node]));
      }
    }
  }
}

// The Class to handle nodes
class Node implements Comparator<Node> {
  public int dj_node;
  public int dj_cost;
  public Node() {}

  public Node(int dj_node, int dj_cost) {
    this.dj_node = dj_node;
    this.dj_cost = dj_cost;
  }
  @Override
  public int compare(Node dj_node1, Node dj_node2) {
    if (dj_node1.dj_cost < dj_node2.dj_cost)
      return -1;
    if (dj_node1.dj_cost > dj_node2.dj_cost)
      return 1;
    return 0;
  }
}

上面的代码将使用 Java 中的 Dijkstra 算法给出给定图的最短路径。

输出：

The shortest paths from source nodes to all other nodes:
Source_Node    Other_Node#    Path_Distance
0              0              0
0              1              5
0              2              3
0              3              6
0              4              2
0              5              7

在 Java 中使用邻接矩阵实现 Dijkstra 算法

这是使用邻接矩阵的 Dijkstra 算法的 Java 实现：

package delftstack;

// Dijkstra's Algorithm using Adjacency matrix  in Java

public class Dijkstra_Algorithm {
  public static void dijkstra_algo(int[][] Input_Graph, int source_node) {
    int Node_Count = Input_Graph.length;
    boolean[] Vertex_Visited = new boolean[Node_Count];
    int[] Node_Distance = new int[Node_Count];
    for (int x = 0; x < Node_Count; x++) {
      Vertex_Visited[x] = false;
      Node_Distance[x] = Integer.MAX_VALUE;
    }

    // Distance of the source node to itself is zero
    Node_Distance[source_node] = 0;
    for (int x = 0; x < Node_Count; x++) {
      // Updating the distance between the source vertex and neighboring vertex
      int ux = findMinDistance(Node_Distance, Vertex_Visited);
      Vertex_Visited[ux] = true;

      // Updating all the neighboring vertices distances
      for (int vx = 0; vx < Node_Count; vx++) {
        if (!Vertex_Visited[vx] && Input_Graph[ux][vx] != 0
            && (Node_Distance[ux] + Input_Graph[ux][vx] < Node_Distance[vx])) {
          Node_Distance[vx] = Node_Distance[ux] + Input_Graph[ux][vx];
        }
      }
    }
    for (int x = 0; x < Node_Distance.length; x++) {
      System.out.println(String.format("Distance from the source node %s to the node %s is %s",
          source_node, x, Node_Distance[x]));
    }
  }

  // Finding the shortest distance
  private static int findMinDistance(int[] Node_Distance, boolean[] Vertex_Visited) {
    int Minimum_Distance = Integer.MAX_VALUE;
    int Minimum_Distance_Vertex = -1;
    for (int x = 0; x < Node_Distance.length; x++) {
      if (!Vertex_Visited[x] && Node_Distance[x] < Minimum_Distance) {
        Minimum_Distance = Node_Distance[x];
        Minimum_Distance_Vertex = x;
      }
    }
    return Minimum_Distance_Vertex;
  }

  public static void main(String[] args) {
    int source_node = 0;
    int Input_Graph[][] = new int[][] {{0, 0, 3, 2, 0, 0, 1}, {0, 0, 2, 0, 4, 1, 0},
        {1, 0, 0, 3, 3, 0, 0}, {2, 0, 1, 0, 5, 0, 1}, {0, 0, 0, 4, 0, 2, 3}, {0, 3, 0, 1, 2, 0, 1},
        {0, 0, 0, 3, 0, 0, 4}};
    Dijkstra_Algorithm Demo = new Dijkstra_Algorithm();
    Demo.dijkstra_algo(Input_Graph, source_node);
  }
}

上面的代码将使用 Java 中的 Dijkstra 算法在邻接矩阵中输出给定图的最短路径。

输出：

Distance from the source node 0 to the node 0 is 0
Distance from the source node 0 to the node 1 is 11
Distance from the source node 0 to the node 2 is 3
Distance from the source node 0 to the node 3 is 2
Distance from the source node 0 to the node 4 is 6
Distance from the source node 0 to the node 5 is 8
Distance from the source node 0 to the node 6 is 1

我们可以使用 Dijkstra 算法的两种方法来计算使用 Java 的图的最短路径。