09.02_最短路径
最短路径
问题描述
最短路径算法用于求解图中两点间的最短距离，包括Dijkstra、Bellman-Ford、Floyd等算法。
Dijkstra算法
算法思想
- 基于贪心策略
- 适用于非负权图
- 可以使用优先队列优化
- 时间复杂度
代码实现
class Solution {
public:
vector<int> dijkstra(vector<vector<pair<int, int>>>& adj, int start) {
int n = adj.size();
vector<int> dist(n, INT_MAX);
dist[start] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
pq.push({0, start});
while (!pq.empty()) {
auto [d, v] = pq.top();
pq.pop();
if (d > dist[v]) continue;
for (auto [u, w] : adj[v]) {
if (dist[v] + w < dist[u]) {
dist[u] = dist[v] + w;
pq.push({dist[u], u});
}
}
}
return dist;
}
};
class Solution {
public int[] dijkstra(List<List<int[]>> adj, int start) {
int n = adj.size();
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
pq.offer(new int[]{0, start});
while (!pq.isEmpty()) {
int[] cur = pq.poll();
int d = cur[0], v = cur[1];
if (d > dist[v]) continue;
for (int[] edge : adj.get(v)) {
int u = edge[0], w = edge[1];
if (dist[v] + w < dist[u]) {
dist[u] = dist[v] + w;
pq.offer(new int[]{dist[u], u});
}
}
}
return dist;
}
}
class Solution:
def dijkstra(self, adj: List[List[Tuple[int, int]]], start: int) -> List[int]:
n = len(adj)
dist = [float('inf')] * n
dist[start] = 0
pq = [(0, start)]
while pq:
d, v = heapq.heappop(pq)
if d > dist[v]:
continue
for u, w in adj[v]:
if dist[v] + w < dist[u]:
dist[u] = dist[v] + w
heapq.heappush(pq, (dist[u], u))
return dist
Floyd算法
算法思想
- 基于动态规划
- 适用于多源最短路
- 可以处理负权边
- 时间复杂度
代码实现
class Solution {
public:
vector<vector<int>> floyd(vector<vector<int>>& graph) {
int n = graph.size();
vector<vector<int>> dist = graph;
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] != INT_MAX && dist[k][j] != INT_MAX) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
return dist;
}
};
class Solution {
public int[][] floyd(int[][] graph) {
int n = graph.length;
int[][] dist = new int[n][n];
// 复制图
for (int i = 0; i < n; i++) {
dist[i] = Arrays.copyOf(graph[i], n);
}
// Floyd算法
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] != Integer.MAX_VALUE &&
dist[k][j] != Integer.MAX_VALUE) {
dist[i][j] = Math.min(dist[i][j],
dist[i][k] + dist[k][j]);
}
}
}
}
return dist;
}
}
class Solution:
def floyd(self, graph: List[List[int]]) -> List[List[int]]:
n = len(graph)
dist = [[x for x in row] for row in graph] # 深拷贝
# Floyd算法
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'):
dist[i][j] = min(dist[i][j],
dist[i][k] + dist[k][j])
return dist
时间复杂度分析
| Dijkstra | ||
| Bellman-Ford | ||
| Floyd | ||
| SPFA |
应用场景
- 导航系统
- 网络路由
- 社交网络
- 资源调度
- 游戏寻路
注意事项
- 权值的正负
- 边界情况
- 溢出处理
- 算法选择
- 优化方式
常见变形
- 带路径记录的Dijkstra
class Solution {
public:
pair<vector<int>, vector<int>> dijkstraWithPath(vector<vector<pair<int, int>>>& adj, int start) {
int n = adj.size();
vector<int> dist(n, INT_MAX);
vector<int> parent(n, -1);
dist[start] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
pq.push({0, start});
while (!pq.empty()) {
auto [d, v] = pq.top();
pq.pop();
if (d > dist[v]) continue;
for (auto [u, w] : adj[v]) {
if (dist[v] + w < dist[u]) {
dist[u] = dist[v] + w;
parent[u] = v;
pq.push({dist[u], u});
}
}
}
return {dist, parent};
}
};
class Solution {
public int[][] dijkstraWithPath(List<List<int[]>> adj, int start) {
int n = adj.size();
int[] dist = new int[n];
int[] parent = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
Arrays.fill(parent, -1);
dist[start] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
pq.offer(new int[]{0, start});
while (!pq.isEmpty()) {
int[] cur = pq.poll();
int d = cur[0], v = cur[1];
if (d > dist[v]) continue;
for (int[] edge : adj.get(v)) {
int u = edge[0], w = edge[1];
if (dist[v] + w < dist[u]) {
dist[u] = dist[v] + w;
parent[u] = v;
pq.offer(new int[]{dist[u], u});
}
}
}
return new int[][]{dist, parent};
}
}
class Solution:
def dijkstraWithPath(self, adj: List[List[Tuple[int, int]]], start: int) -> Tuple[List[int], List[int]]:
n = len(adj)
dist = [float('inf')] * n
parent = [-1] * n
dist[start] = 0
pq = [(0, start)]
while pq:
d, v = heapq.heappop(pq)
if d > dist[v]:
continue
for u, w in adj[v]:
if dist[v] + w < dist[u]:
dist[u] = dist[v] + w
parent[u] = v
heapq.heappush(pq, (dist[u], u))
return dist, parent
- 判断负环
class Solution {
public:
bool hasNegativeCycle(vector<vector<pair<int, int>>>& adj) {
int n = adj.size();
vector<int> dist(n);
// 进行n-1次松弛
for (int i = 0; i < n - 1; i++) {
for (int v = 0; v < n; v++) {
for (auto [u, w] : adj[v]) {
if (dist[v] + w < dist[u]) {
dist[u] = dist[v] + w;
}
}
}
}
// 检查是否还能继续松弛
for (int v = 0; v < n; v++) {
for (auto [u, w] : adj[v]) {
if (dist[v] + w < dist[u]) {
return true; // 存在负环
}
}
}
return false;
}
};
class Solution {
public boolean hasNegativeCycle(List<List<int[]>> adj) {
int n = adj.size();
int[] dist = new int[n];
// 进行n-1次松弛
for (int i = 0; i < n - 1; i++) {
for (int v = 0; v < n; v++) {
for (int[] edge : adj.get(v)) {
int u = edge[0], w = edge[1];
if (dist[v] + w < dist[u]) {
dist[u] = dist[v] + w;
}
}
}
}
// 检查是否还能继续松弛
for (int v = 0; v < n; v++) {
for (int[] edge : adj.get(v)) {
int u = edge[0], w = edge[1];
if (dist[v] + w < dist[u]) {
return true; // 存在负环
}
}
}
return false;
}
}
class Solution:
def hasNegativeCycle(self, adj: List[List[Tuple[int, int]]]) -> bool:
n = len(adj)
dist = [0] * n
# 进行n-1次松弛
for i in range(n - 1):
for v in range(n):
for u, w in adj[v]:
if dist[v] + w < dist[u]:
dist[u] = dist[v] + w
# 检查是否还能继续松弛
for v in range(n):
for u, w in adj[v]:
if dist[v] + w < dist[u]:
return True # 存在负环
return False
经典例题
牛客代码笔记-牛栋 文章被收录于专栏
汗牛充栋，学海无涯。<br/> 内含算法知识点讲解，以及牛客题库精选例题。<br/> 学习算法，从牛栋开始。
飞鱼科技一面29人在聊
投递美团等公司10个岗位
滴滴公司福利 605人发布