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:
代码语言：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 "tt" 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 "tt" 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代码
代码语言：txt复制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
