最短路径问题是图论中的一个经典问题，它寻找图中两点之间的最短路径。这个问题在现实世界中有广泛的应用，比如导航系统中的路线规划、网络中的信息传输等。解决最短路径问题有多种算法，其中最著名的包括：
贝尔曼-福特算法（Bellman-Ford）：可以处理带有负权边的图，通过迭代松弛操作计算从单一源点到所有其他顶点的最短路径。
迪杰斯特拉算法（Dijkstra’s Algorithm）：适用于没有负权边的图，使用贪心策略和优先队列（或二叉堆）来找到单源最短路径。
弗洛伊德算法（Floyd-Warshall）：计算所有顶点对之间的最短路径，适用于密集图。
A*搜索算法：结合了迪杰斯特拉算法和启发式搜索，常用于图搜索和路径规划问题，特别是在有明确目标的情况下。
贝尔曼-福特算法的Java实现：
public class BellmanFord {
public int[] bellmanFord(int n, int[][] edges, int src) {
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
for (int i = 0; i < n - 1; i++) {
for (int[] edge : edges) {
int u = edge[0], v = edge[1], weight = edge[2];
if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
}
}
}
// 检测负权环
for (int[] edge : edges) {
if (dist[edge[0]] != Integer.MAX_VALUE && dist[edge[0]] + edge[2] < dist[edge[1]]) {
throw new IllegalArgumentException("Graph contains a negative-weight cycle");
}
}
return dist;
}
public static void main(String[] args) {
BellmanFord bf = new BellmanFord();
int n = 5;
int[][] edges = {{0, 1, -1}, {0, 2, 4}, {1, 2, 3}, {1, 3, 2}, {1, 4, 2}, {3, 4, -5}};
int src = 0;
int[] dist = bf.bellmanFord(n, edges, src);
System.out.println("Single source shortest path distances: " + Arrays.toString(dist));
}
}
迪杰斯特拉算法的Java实现：
import java.util.PriorityQueue;
public class Dijkstra {
public int[] dijkstra(int n, int[][] edges, int src) {
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>(n, (a, b) -> a[1] - b[1]);
pq.offer(new int[]{src, 0});
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int node = curr[0], weight = curr[1];
if (weight == dist[node]) {
for (int[] edge : edges) {
if (node == edge[0]) {
int nextNode = edge[1], edgeWeight = edge[2];
pq.offer(new int[]{nextNode, dist[node] + edgeWeight});
}
}
}
}
return dist;
}
public static void main(String[] args) {
Dijkstra dijkstra = new Dijkstra();
int n = 5;
int[][] edges = {{0, 1, 10}, {0, 2, 4}, {1, 2, 3}, {1, 3, 2}, {1, 4, 2}, {3, 4, 5}};
int src = 0;
int[] dist = dijkstra.dijkstra(n, edges, src);
System.out.println("Single source shortest path distances: " + Arrays.toString(dist));
}
}
面试大厂题示例：
单源最短路径：
描述：给定一个加权图，找到从单一源点到所有其他顶点的最短路径。带有负权边的最短路径：
描述：给定一个带有负权边的图，找到从单一源点到所有其他顶点的最短路径。检测负权环：
描述：给定一个图，使用一种算法检测图中是否存在负权环。所有顶点对的最短路径：
描述：给定一个图，找到所有顶点对之间的最短路径。最短路径计数：
描述：给定一个无向无权图，计算从源点到每个顶点的最短路径数量。
在面试中，最短路径问题是考察候选人对图算法和动态规划理解的常见方式。通过实现最短路径算法，可以展示你对算法设计和优化的掌握程度。希望这些示例能够帮助你更好地准备面试！最短路径问题在大厂面试中经常出现，因为它们考察了应聘者对图算法的理解和实现能力。以下是三道与最短路径相关的面试题目，以及相应的Java源码实现。
题目 1：单源最短路径
描述：
给定一个加权有向图，找到从单一源点到所有其他顶点的最短路径。
示例：
输入：图的邻接矩阵表示，源点为 0
[
[0, 4, 0, 0, 0],
[4, 0, 8, 0, 0],
[0, 8, 0, 5, 0],
[0, 0, 5, 0, 10],
[0, 0, 0, 10, 0]
]
输出：最短路径长度数组 [0, 4, 8, 3, 9]
Java 源码（使用Dijkstra算法）：
import java.util.PriorityQueue;
import java.util.Arrays;
public class SingleSourceShortestPath {
public int[] dijkstra(int[][] graph, int src) {
int n = graph.length;
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
PriorityQueue<int[]> pq = new PriorityQueue<>(n, (a, b) -> a[1] - b[1]);
pq.offer(new int[]{src, 0});
dist[src] = 0;
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int node = curr[0], cost = curr[1];
for (int i = 0; i < n; i++) {
if (graph[node][i] > 0 && dist[node] + graph[node][i] < dist[i]) {
dist[i] = dist[node] + graph[node][i];
pq.offer(new int[]{i, dist[i]});
}
}
}
return dist;
}
public static void main(String[] args) {
SingleSourceShortestPath solution = new SingleSourceShortestPath();
int[][] graph = {
{0, 4, 0, 0, 0},
{4, 0, 8, 0, 0},
{0, 8, 0, 5, 0},
{0, 0, 5, 0, 10},
{0, 0, 0, 10, 0}
};
int[] result = solution.dijkstra(graph, 0);
System.out.println("Shortest path lengths: " + Arrays.toString(result));
}
}
题目 2：带有负权边的最短路径
描述：
给定一个带有负权边的加权有向图，找到从单一源点到所有其他顶点的最短路径。如果存在负权环，则无法找到最短路径。
示例：
输入：图的邻接矩阵表示，源点为 0
[
[0, -1, 0, 0, 0],
[-1, 0, -2, 0, 0],
[0, -2, 0, -3, 0],
[0, 0, -3, 0, 4],
[0, 0, 0, 4, 0]
]
输出：最短路径长度数组 [0, -1, -3, -6, 2]
Java 源码（使用Bellman-Ford算法）：
import java.util.Arrays;
public class NegativeWeightShortestPath {
public int[] 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 = 0; i < n - 1; 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];
}
}
}
}
// Check for negative-weight cycles
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]) {
throw new IllegalStateException("Graph contains a negative-weight cycle");
}
}
}
return dist;
}
// main 方法与题目 1 类似
}
题目 3：所有顶点对的最短路径
描述：
给定一个加权有向图，找到所有顶点对之间的最短路径。
示例：
输入：图的邻接矩阵表示
[
[0, 5, 0, 10],
[0, 0, 3, 0],
[0, 0, 0, 2],
[0, 0, 0, 0]
]
输出：所有顶点对的最短路径长度矩阵
Java 源码（使用Floyd-Warshall算法）：
public class AllPairsShortestPath {
public int[][] 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] = (i == j) ? 0 : Integer.MAX_VALUE;
}
}
// Fill the distance matrix with edge weights
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (graph[i][k] != 0 && graph[k][j] != 0 && dist[i][k] + graph[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + graph[k][j];
}
}
}
}
return dist;
}
public static void main(String[] args) {
AllPairsShortestPath solution = new AllPairsShortestPath();
int[][] graph = {
{0, 5, 0, 10},
{0, 0, 3, 0},
{0, 0, 0, 2},
{0, 0, 0, 0}
};
int[][] result = solution.floydWarshall(graph);
System.out.println("All pairs shortest path lengths: " + Arrays.deepToString(result));
}
}
这些题目和源码展示了最短路径问题的不同变体以及如何在实际编程中解决它们。在面试中，能够根据问题的特点选择合适的算法并实现其解决方案是非常重要的。希望这些示例能够帮助你更好地准备面试！