如何实现最短路径算法？Dijkstra算法实现

最短路径算法是指在一个有向加权图中，找出从起点到终点的最短路径。常见的解决方案有两种：Dijkstra算法和Bellman-Ford算法。

Dijkstra算法

Dijkstra算法是一种贪心算法，它通过维护一个距离起点最短的顶点集合S，逐步扩展这个集合，直到包含终点为止。在每次扩展时，将S中的顶点与它们的邻居进行松弛操作，更新它们到起点的距离值。

下面是Dijkstra算法的Java实现：

import java.util.*;

public class Dijkstra {
    public static int shortestPath(int[][] graph, int source, int target) {
        int n = graph.length;
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[source] = 0;
        boolean[] visited = new boolean[n];
        PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.comparingInt(i -> dist[i]));
        queue.offer(source);
        while (!queue.isEmpty()) {
            int u = queue.poll();
            if (u == target) {
                return dist[u];
            }
            visited[u] = true;
            for (int v = 0; v < n; v++) {
                if (graph[u][v] != 0 && !visited[v]) {
                    int newDist = dist[u] + graph[u][v];
                    if (newDist < dist[v]) {
                        dist[v] = newDist;
                        queue.offer(v);
                    }
                }
            }
        }
        return -1;
    }
}