单元最短路径算法Java

元最短路径算法是指在一个加权有向图或者无向图中，从一个源点到所有其他顶点的最短路径算法。其中，边的权重必须为非负数。Java中可以使用Dijkstra算法和Bellman-Ford算法来实现单元最短路径算法。

Dijkstra算法的基本思想是：设立一个集合S，存放已经求得最短路径的顶点，以及一个数组dist，表示源点到各个顶点的最短距离。初始时，集合S中只有源点，dist数组中除了源点为0外，其余元素都为无穷大。然后，每次从dist数组中选择最小值对应的顶点，加入集合S中，并更新dist数组。具体实现可以使用优先队列来优化时间复杂度。

Bellman-Ford算法的基本思想是：设立一个数组dist，表示源点到各个顶点的最短距离，初始时，dist数组中除了源点为0外，其余元素都为无穷大。然后，对于每一条边(u,v)，如果dist[u]+w(u,v)<dist[v]，则更新dist[v]为dist[u]+w(u,v)。重复执行V-1次后，如果还存在dist[u]+w(u,v)<dist[v]的情况，则说明存在负权回路。

下面是Java代码示例：

// Dijkstra算法
public void dijkstra(int[][] graph, int src) {
    int n = graph.length;
    int[] dist = new int[n];
    boolean[] visited = new boolean[n];
    PriorityQueue<Integer> pq = new PriorityQueue<>(n, (a, b) -> dist[a] - dist[b]);
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    pq.offer(src);
    while (!pq.isEmpty()) {
        int u = pq.poll();
        if (visited[u]) {
            continue;
        }
        visited[u] = true;
        for (int v = 0; v < n; v++) {
            if (graph[u][v] > 0 && !visited[v] && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
                pq.offer(v);
            }
        }
    }
}

// Bellman-Ford算法
public void bellmanFord(int[][] graph, int src) {
    int n = graph.length;
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    for (int i = 1; i < n; i++) {
        for (int u = 0; u < n; u++) {
            for (int v = 0; v < n; v++) {
                if (graph[u][v] > 0 && dist[u] != Integer.MAX_VALUE && dist[u] + graph[u][v] < dist[v]) {
                    dist[v] = dist[u] + graph[u][v];
                }
            }
        }
    }
    for (int u = 0; u < n; u++) {
        for (int v = 0; v < n; v++) {
            if (graph[u][v] > 0 && dist[u] != Integer.MAX_VALUE && dist[u] + graph[u][v] < dist[v]) {
                System.out.println("图中存在负权回路");
                return;
            }
        }
    }
}