Java实现最短路径计算 |21xrx.com

Java实现最短路径计算

2023-06-15 00:28:44 深夜i -- --

Java 最短路径 Dijkstra算法

在计算机科学领域中，最短路径问题是一类经典的算法问题。它经常在地图、网络、运输等业务场景中得到应用。Java 是一门流行的编程语言，由于其强大的计算能力，它在解决最短路径问题上得到了广泛的应用。

本文将介绍如何在Java中计算最短路径。我们将使用最经典的最短路径算法——Dijkstra算法。在此之前，我们需要了解一下Java中实现图的数据结构。Java中的图可以使用邻接矩阵或者邻接表来表示。我们这里采用邻接表的方式来实现：

public class Node {
  int val;
  int weight;
  public Node(int val, int weight)
    this.val = val;
    this.weight = weight;
  
}
public class Graph {
  List
  
   > adjList;
  
 
  public Graph(int n) {
    adjList = new ArrayList<>(n);
    for (int i = 0; i < n; i++) {
      adjList.add(new ArrayList<>());
    }
  }
  public void addEdge(int u, int v, int weight) {
    adjList.get(u).add(new Node(v, weight));
  }
}

上述代码定义了一个 `Graph` 类，其中`adjList`是邻接表的形式。每个节点都是使用`Node`表示，其中`val`表示节点的序号，`weight`表示节点之间的权重。我们可以通过调用`addEdge`方法来添加新的边。

为了简化代码规模，我们这里考虑一个有向有权图。那么我们可以用Dijkstra算法求解节点0到n-1之间的最短路径：

public class Dijkstra {
  public int shortestPath(Graph graph, int source, int destination) {
    PriorityQueue
  pq = new PriorityQueue<>(Comparator.comparingInt(a -> a.weight));
 
    pq.add(new Node(source, 0));
    Set
  seen = new HashSet<>();
 
    while (!pq.isEmpty()) {
      Node cur = pq.poll();
      if (cur.val == destination)
        return cur.weight;
      
      if (seen.contains(cur.val))
        continue;
      
      seen.add(cur.val);
      for (Node next : graph.adjList.get(cur.val)) {
        if (!seen.contains(next.val)) {
          pq.add(new Node(next.val, cur.weight + next.weight));
        }
      }
    }
    return -1;
  }
}

上述代码定义了一个 `Dijkstra` 类，其中`shortestPath` 方法使用了优先队列。我们每次从队列中找出当前路径最短的节点，并处理其周围的节点。然后将周围可达节点加入队列中，以此逐渐扩展路径。如果最后我们找到了终点，返回当前路径长度；否则返回-1表示无法到达。

在我们的情景下，我们有一个邻接表的图，并要从0出发到n-1的一个目标。现在，我们只需要调用`shortestPath`方法：

public static void main(String[] args) {
  Graph g = new Graph(5);
  g.addEdge(0,1,1);
  g.addEdge(0,2,3);
  g.addEdge(1,3,2);
  g.addEdge(2,4,1);
  g.addEdge(3,4,2);
  g.addEdge(4,1,1);
  Dijkstra dijkstra = new Dijkstra();
  int shortestPath = dijkstra.shortestPath(g, 0, 4);
  System.out.println(shortestPath);
}

以上代码定义了一个大小为5的图，并添加了6条边。我们从节点0出发，寻找到节点4的最短路径。程序输出的结果为4，即从节点0到节点4的最短路径长度为4。

上一篇: idea打包java可执行jar包

下一篇: Java实现文件内容写入的方法及代码案例

评论区

相似文章