java python双语言实现5种最短路径算法

Dijkstra算法：

使用二进制堆而不是优先级队列来优化运行时的复杂性。

使用邻接列表而不是邻接矩阵，以避免访问不必要的顶点。

Bellman-Ford算法：

使用邻接列表来优化运行时的复杂性。

如果在迭代过程中没有发生任何更改，请提前退出循环，以避免迭代次数超过必要次数。

Floyd-Warshall算法：

如果顶点数量较少，请使用邻接矩阵而不是边列表。

如果可用的处理器数量大于顶点数量，请使用并行处理同时计算最短路径。

约翰逊算法：

使用二进制堆或斐波那契堆来优化Dijkstra算法的运行时复杂性。

通过使用修改的Bellman-Ford算法，避免在初始松弛步骤期间对图中的所有边进行迭代，该算法只处理在上一次迭代中更新的顶点。

A*搜索算法：

使用邻接列表而不是矩阵来避免访问不必要的顶点。

使用二进制堆或斐波那契堆来优化搜索算法的运行时复杂性。

优化代码将显著提高Java中五种最短路径算法的性能。

Implementing five shortest path algorithms using java code

Here are five shortest path algorithms implemented in Java:

Dijkstra's Algorithm
import java.util.*;

public class Dijkstra {
    private static final int INFINITY = Integer.MAX_VALUE;
    
    public static void dijkstra(int[][] graph, int start) {
        int n = graph.length;
        int[] dist = new int[n];
        boolean[] visited = new boolean[n];
        
        Arrays.fill(dist, INFINITY);
        dist[start] = 0;
        
        for (int i = 0; i < n - 1; i++) {
            int u = getMinDistance(dist, visited);
            visited[u] = true;
            
            for (int v = 0; v < n; v++) {
                if (!visited[v] && graph[u][v] != 0 && 
                        dist[u] != INFINITY && dist[u] + graph[u][v] < dist[v]) {
                    dist[v] = dist[u] + graph[u][v];
                }
            }
        }
        
        printDistances(dist);
    }
    
    private static int getMinDistance(int[] dist, boolean[] visited) {
        int min = INFINITY;
        int minIndex = -1;
        
        for (int i = 0; i < dist.length; i++) {
            if (!visited[i] && dist[i] < min) {
                min = dist[i];
                minIndex = i;
            }
        }
        
        return minIndex;
    }
    
    private static void printDistances(int[] dist) {
        System.out.println("Vertex   Distance from Source");
        for (int i = 0; i < dist.length; i++) {
            System.out.println(i + "\t\t" + dist[i]);
        }
    }
}
Bellman-Ford Algorithm
import java.util.*;

public class BellmanFord {
    private static final int INFINITY = Integer.MAX_VALUE;
    
    public static void bellmanFord(int[][] graph, int start) {
        int n = graph.length;
        int[] dist = new int[n];
        
        Arrays.fill(dist, INFINITY);
        dist[start] = 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] != INFINITY && 
                            dist[u] + graph[u][v] < dist[v]) {
                        dist[v] = dist[u] + graph[u][v];
                    }
                }
            }
        }
        
        printDistances(dist);
    }
    
    private static void printDistances(int[] dist) {
        System.out.println("Vertex   Distance from Source");
        for (int i = 0; i < dist.length; i++) {
            System.out.println(i + "\t\t" + dist[i]);
        }
    }
}
Floyd-Warshall Algorithm
import java.util.*;

public class FloydWarshall {
    private static final int INFINITY = Integer.MAX_VALUE;
    
    public static void floydWarshall(int[][] graph) {
        int n = graph.length;
        int[][] dist = new int[n][n];
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist[i][j] = graph[i][j];
            }
        }
        
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dist[i][k] != INFINITY && dist[k][j] != INFINITY &&
                            dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
        
        printDistances(dist);
    }
    
    private static void printDistances(int[][] dist) {
        System.out.println("Pairs    Shortest Distance");
        for (int i = 0; i < dist.length; i++) {
            for (int j = 0; j < dist.length; j++) {
                System.out.println(i + " -> " + j + "   " + dist[i][j]);
            }
        }
    }
}
Johnson's Algorithm
import java.util.*;

public class Johnson {
    private static final int INFINITY = Integer.MAX_VALUE;
    
    public static void johnson(int[][] graph) {
        int n = graph.length;
        List<Edge> edges = new ArrayList<>();
        int[] h = new int[n];
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (graph[i][j] != 0) {
                    edges.add(new Edge(i, j, graph[i][j]));
                }
            }
        }
        
        for (int i = 0; i < n; i++) {
            edges.add(new Edge(n, i, 0));
        }
        
        if (!bellmanFord(edges, n, h)) {
            System.out.println("Graph contains negative-weight cycles");
            return;
        }
        
        int[][] dist = new int[n][n];
        
        for (int i = 0; i < n; i++) {
            int[] dij = dijkstra(graph, i);
            for (int j = 0; j < n; j++) {
                if (dij[j] != INFINITY) {
                    dist[i][j] = dij[j] - h[i] + h[j];
                }
            }
        }
        
        printDistances(dist);
    }
    
    private static int[] dijkstra(int[][] graph, int start) {
        int n = graph.length;
        int[] dist = new int[n];
        boolean[] visited = new boolean[n];
        
        Arrays.fill(dist, INFINITY);
        dist[start] = 0;
        
        for (int i = 0; i < n - 1; i++) {
            int u = getMinDistance(dist, visited);
            visited[u] = true;
            
            for (int v = 0; v < n; v++) {
                if (!visited[v] && graph[u][v] != 0 && 
                        dist[u] != INFINITY && dist[u] + graph[u][v] < dist[v]) {
                    dist[v] = dist[u] + graph[u][v];
                }
            }
        }
        
        return dist;
    }
    
    private static boolean bellmanFord(List<Edge> edges, int n, int[] h) {
        Arrays.fill(h, INFINITY);
        h[n] = 0;
        
        for (int i = 1; i < n; i++) {
            for (Edge e : edges) {
                if (h[e.from] != INFINITY && h[e.from] + e.weight < h[e.to]) {
                    h[e.to] = h[e.from] + e.weight;
                }
            }
        }
        
        for (Edge e : edges) {
            if (h[e.from] != INFINITY && h[e.from] + e.weight < h[e.to]) {
                return false;
            }
        }
        
        return true;
    }
    
    private static int getMinDistance(int[] dist, boolean[] visited) {
        int min = INFINITY;
        int minIndex = -1;
        
        for (int i = 0; i < dist.length; i++) {
            if (!visited[i] && dist[i] < min) {
                min = dist[i];
                minIndex = i;
            }
        }
        
        return minIndex;
    }
    
    private static void printDistances(int[][] dist) {
        System.out.println("Pairs    Shortest Distance");
        for (int i = 0; i < dist.length; i++) {
            for (int j = 0; j < dist.length; j++) {
                System.out.println(i + " -> " + j + "   " + dist[i][j]);
            }
        }
    }
    
    private static class Edge {
        int from;
        int to;
        int weight;
        
        public Edge(int from, int to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }
}
A* Search Algorithm
import java.util.*;

public class AStar {
    private static final int INFINITY = Integer.MAX_VALUE;
    
    public static void aStar(int[][] graph, int start, int end, int[] heuristic) {
        int n = graph.length;
        int[] dist = new int[n];
        int[] cost = new int[n];
        PriorityQueue<Integer> queue = new PriorityQueue<>(n, new Comparator<Integer>() {
            @Override
            public int compare(Integer u, Integer v) {
                return cost[u] - cost[v];
            }
        });
        boolean[] visited = new boolean[n];
        int[] parent = new int[n];
        
        Arrays.fill(dist, INFINITY);
        Arrays.fill(cost, INFINITY);
        dist[start] = 0;
        cost[start] = heuristic[start];
        queue.offer(start);
        
        while (!queue.isEmpty()) {
            int u = queue.poll();
            visited[u] = true;
            
            if (u == end) {
                printPath(parent, end);
                return;
            }
            
            for (int v = 0; v < n; v++) {
                if (!visited[v] && graph[u][v] != 0 && dist[u] != INFINITY &&
                        dist[u] + graph[u][v] < dist[v]) {
                    dist[v] = dist[u] + graph[u][v];
                    parent[v] = u;
                    cost[v] = dist[v] + heuristic[v];
                    queue.offer(v);
                }
            }
        }
        
        System.out.println("Path does not exist");
    }
    
    private static void printPath(int[] parent, int end) {
        List<Integer> path = new ArrayList<>();
        int current = end;
        
        while (current != -1) {
            path.add(current);
            current = parent[current];
        }
        
        System.out.print("Path: ");
        for (int i = path.size() - 1; i >= 0; i--) {
            System.out.print(path.get(i) + " ");
        }
    }
}

Python代码

Here are five shortest path algorithms implemented in Python:

Dijkstra's Algorithm
import heapq

def dijkstra(graph, start):
    n = len(graph)
    dist = [float('inf')] * n
    dist[start] = 0
    visited = [False] * n
    heap = [(0, start)]

    while heap:
        u_dist, u = heapq.heappop(heap)
        visited[u] = True

        for v in range(n):
            if graph[u][v] != 0 and not visited[v]:
                alt_dist = u_dist + graph[u][v]
                if alt_dist < dist[v]:
                    dist[v] = alt_dist
                    heapq.heappush(heap, (dist[v], v))

    return dist
Bellman-Ford Algorithm
def bellman_ford(graph, start):
    n = len(graph)
    dist = [float('inf')] * n
    dist[start] = 0

    for i in range(n - 1):
        for u in range(n):
            for v in range(n):
                if graph[u][v] != 0 and dist[u] != float('inf') and dist[u] + graph[u][v] < dist[v]:
                    dist[v] = dist[u] + graph[u][v]

    return dist
Floyd-Warshall Algorithm
def floyd_warshall(graph):
    n = len(graph)
    dist = [[float('inf')] * n for _ in range(n)]

    for i in range(n):
        for j in range(n):
            if i == j:
                dist[i][j] = 0
            elif graph[i][j] != 0:
                dist[i][j] = graph[i][j]

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] != float('inf') and dist[k][j] != float('inf') and dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist
Johnson's Algorithm
import heapq

def johnson(graph):
    n = len(graph)
    edges = []
    h = [float('inf')] * n

    for i in range(n):
        for j in range(n):
            if graph[i][j] != 0:
                edges.append((i, j, graph[i][j]))

    for i in range(n):
        edges.append((n, i, 0))

    if not bellman_ford_edges(edges, n, h):
        print("Graph contains negative-weight cycles")
        return None

    dist = [[float('inf')] * n for _ in range(n)]

    for i in range(n):
        dij = dijkstra(graph, i)
        for j in range(n):
            if dij[j] != float('inf'):
                dist[i][j] = dij[j] - h[i] + h[j]

    return dist

def dijkstra(graph, start):
    n = len(graph)
    dist = [float('inf')] * n
    dist[start] = 0
    heap = [(0, start)]

    while heap:
        u_dist, u = heapq.heappop(heap)

        for v in range(n):
            if graph[u][v] != 0:
                alt_dist = u_dist + graph[u][v]
                if alt_dist < dist[v]:
                    dist[v] = alt_dist
                    heapq.heappush(heap, (dist[v], v))

    return dist

def bellman_ford_edges(edges, start, h):
    n = len(h)
    h[start] = 0

    for i in range(n - 1):
        for u, v, w in edges:
            if h[u] != float('inf') and h[u] + w < h[v]:
                h[v] = h[u] + w

    for u, v, w in edges:
        if h[u] != float('inf') and h[u] + w < h[v]:
            return False

    return True
A* Search Algorithm
import heapq

def a_star(graph, start, end, heuristic):
    n = len(graph)
    dist = [float('inf')] * n
    cost = [float('inf')] * n
    heap = [(heuristic[start], start)]
    visited = [False] * n
    parent = [-1] * n
    dist[start] = 0
    cost[start] = heuristic[start]

    while heap:
        _, u = heapq.heappop(heap)
        visited[u] = True

        if u == end:
            return get_path(parent, start, end)

        for v in range(n):
            if graph[u][v] != 0 and not visited[v]:
                alt_dist = dist[u] + graph[u][v]
                alt_cost = alt_dist + heuristic[v]
                if alt_cost < cost[v]:
                    dist[v] = alt_dist
                    cost[v] = alt_cost
                    parent[v] = u
                    heapq.heappush(heap, (alt_cost, v))

    return None

def get_path(parent, start, end):
    path = []
    current = end

    while current != -1:
        path.append(current)
        current = parent[current]

    path.reverse()
    return path