单源最短路径【学习算法】
- 前言
- 版权
- 推荐
- 单源最短路径
- Java算法实现
- 代码
- 结果
- 带限制的单源最短路径
- 1928. 规定时间内到达终点的最小花费
- LCP 35. 电动车游城市
- 最后
前言
2023-8-14 18:21:41
推荐
第七章 图【数据结构与算法】
单源最短路径
Java算法实现
代码
import java.util.*;
/**
* 在这个代码模板中，我们通过遍历int[] paths来构建图的邻接表。
* 每个元素paths[i]表示从顶点paths[i][0]到顶点paths[i][1]的距离为paths[i][2]。
*
* 我们使用一个ArrayList来表示图的邻接表，每个顶点都有一个对应的列表，其中存储了与该顶点相连的边的目标顶点及其权重。
*
* 然后，我们可以使用Dijkstra算法来计算从给定起始顶点到其他顶点的最短距离。
* 算法的时间复杂度为O((V+E)logV)，其中V为顶点的数量，E为边的数量。
*
* 这个代码模板使用了优先队列来实现最小堆，以提高算法的效率。算法的时间复杂度为O(ElogV)，其中E为边的数量，V为顶点的数量。
*/
public class Dijkstra {
public static void main(String[] args) {
//
int[][] paths = {{0, 1, 2}, {0, 2, 4}, {1, 2, 1}, {1, 3, 4}, {1, 4, 2}, {2, 4, 3}, {3, 5, 2}, {4, 3, 3}, {4, 5, 2}};
int n = 6;
int[] dist = dijkstra(paths, n, 0);
System.out.println(Arrays.toString(dist));
int distD = dijkstraD(paths, n, 0,n-1);
System.out.println(distD);
}
public static int[] dijkstra(int[][] paths, int n, int start) {
//邻接表
List<int[]>[] graph = new ArrayList[n];
//初始化
for (int i = 0; i < n; i++) {
graph[i] = new ArrayList<>();
}
//初始化
for (int[] path : paths) {
int source = path[0];
int destination = path[1];
int weight = path[2];
graph[source].add(new int[]{destination, weight});
graph[destination].add(new int[]{source, weight});
}
//距离
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0;
//优先队列
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
//表示到达顶点 最小距离
pq.offer(new int[]{start, 0});
while (!pq.isEmpty()) {
//取出
int[] curr = pq.poll();
int vertex = curr[0];
int distance = curr[1];
//跳过
if (distance > dist[vertex]) {
continue;
}
//更新
for (int[] edge : graph[vertex]) {
int newDistance = distance + edge[1];
if (newDistance < dist[edge[0]]) {
dist[edge[0]] = newDistance;
pq.offer(new int[]{edge[0], newDistance});
}
}
}
return dist;
}
public static int dijkstraD(int[][] paths,int n, int start,int end) {
//邻接表
List<int[]>[] graph = new ArrayList[n];
//初始化
for (int i = 0; i < n; i++) {
graph[i] = new ArrayList<>();
}
//初始化
for (int[] path : paths) {
int source = path[0];
int destination = path[1];
int weight = path[2];
graph[source].add(new int[]{destination, weight});
graph[destination].add(new int[]{source, weight});
}
//距离
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0;
//优先队列
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
//表示到达顶点 最小距离
pq.offer(new int[]{start, 0});
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int vertex = curr[0];
int distance = curr[1];
if (distance > dist[vertex]) {
continue;
}
if (vertex==end){
return distance;
}
for (int[] edge : graph[vertex]) {
int newDistance = distance + edge[1];
if (newDistance < dist[edge[0]]) {
dist[edge[0]] = newDistance;
pq.offer(new int[]{edge[0], newDistance});
}
}
}
return dist[end];
}
}结果
[0, 2, 3, 6, 4, 6]
6带限制的单源最短路径
1928. 规定时间内到达终点的最小花费
class Solution {
/*
带限制的最短路径操作
其实就是最短路径算法的变化版本，这里带限制的条件使得我们在向对应的队列加入元素的时候需要进行一定的判断，
只有能够帮助我们的答案达到更优的操作才能够加入到队列当中，否则就会由于加入过多的元素导致最终超时。
作者：豆小科
链接：https://leetcode.cn/problems/minimum-cost-to-reach-destination-in-time/solutions/2224593/dai-xian-zhi-de-zui-duan-lu-jing-cao-zuo-d7t6/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/
public static int minCost(int maxTime, int[][] edges, int[] passingFees) {
// 使用最短路径进行处理
int n = passingFees.length;
//构造图邻接表
List<List<int[]>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
for (int[] edge : edges) {
int x = edge[0];
int y = edge[1];
int time = edge[2];
graph.get(x).add(new int[]{y, time});
graph.get(y).add(new int[]{x, time});
}
//优先队列
PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
//时间 花费 当前结点
queue.add(new int[]{0, passingFees[0], 0});
//到达node的最少时间
Map<Integer, Integer> timeMap = new HashMap<>();
while (!queue.isEmpty()) {
int[] poll = queue.poll();
int time = poll[0];
int ct = poll[1];
int node = poll[2];
//继续
if (time > maxTime) continue;
//结束
if (node == n - 1) return ct;
//更新
if (!timeMap.containsKey(node) || timeMap.get(node) > time) {
timeMap.put(node, time);
for (int[] e : graph.get(node)) {
queue.add(new int[]{e[1] + time, passingFees[e[0]] + ct, e[0]});
}
}
}
return -1;
}
}LCP 35. 电动车游城市
/**
* 首先建图， 存储每个城市相邻的城市和距离
*
* 使用一个二维数组保存结果arr[i][j] = k， i = 所在城市， j = 剩余电量， k = 最短时间
*
* 用队列来记录每个路径的信息 {time,cur,power}， time = 已用时间， cur = 所在城市， power = 剩余电量 (使用优先队列来保证每次优先执行已用时间最少的路径)
*
* 每次只会有两种操作
*
* 充一次电 - 新时间 = 已用时间 + 当前城市每单位充电需要时间， 新电量 = 剩余电量 + 1
* 去往下一个城市 - 新时间 = 已用时间 + 去往该需要消耗的时间， 新电量 = 剩余电量 − 去往该城市需要消耗的电量
*
* 作者：Feilulue 🍒
* 链接：https://leetcode.cn/problems/DFPeFJ/solutions/974051/java-dijkstra-by-feilue-8p14/
* 来源：力扣（LeetCode）
* 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/
class Solution {
public int electricCarPlan(int[][] paths, int cnt, int start, int end, int[] charge) {
int n = charge.length;
//构造了图
List<int[]>[] map = new List[n];
for(int i = 0; i < n; i++) map[i] = new ArrayList();
for(int[] path : paths){
map[path[0]].add(new int[]{path[1], path[2]});
map[path[1]].add(new int[]{path[0], path[2]});
}
//使用一个二维数组保存结果arr[i][j] = k
//i = 所在城市， j = 剩余电量， k = 最短时间
int[][] res = new int[n][cnt+1];
for(int[] i : res) Arrays.fill(i, Integer.MAX_VALUE/2);
res[start][0] = 0;
//用队列来记录每个路径的信息 {time,cur,power}，
//time = 已用时间， cur = 所在城市， power = 剩余电量
//(使用优先队列来保证每次优先执行已用时间最少的路径)
Queue<int[]> queue = new PriorityQueue<int[]>((x, y) -> (x[0] - y[0]));
queue.offer(new int[]{0, start, 0});
while(!queue.isEmpty()){
//取出来
int[] arr = queue.poll();
int time = arr[0];
int cur = arr[1];
int power = arr[2];
//继续
if(time > res[cur][power]) continue;
//结束
if(cur == end) return time;
//充一次电
//新时间 = 已用时间 + 当前城市每单位充电需要时间， 新电量 = 剩余电量 + 1
if(power < cnt){
int t = time + charge[cur];
if(t < res[cur][power+1]){
res[cur][power+1] = t;
queue.offer(new int[]{t, cur, power+1});
}
}
//去往下一个城市
//新时间 = 已用时间 + 去往该需要消耗的时间， 新电量 = 剩余电量 − 去往该城市需要消耗的电量
for(int[] path : map[cur]){
int next = path[0];
int cost = path[1];
int t = time + cost;
int p = power - cost;
if(p >= 0 && t < res[next][p]){
res[next][p] = t;
queue.offer(new int[]{t, next, p});
}
}
}
return -1;
}
}最后
我们都有光明的未来
祝大家考研上岸
祝大家工作顺利
祝大家得偿所愿
祝大家如愿以偿
点赞收藏关注哦