力扣-最短路
力扣-最短路
这里介绍三种算法，包括适用于稀疏图与边关系密切且能处理负权的BellmanFord算法，适用于稠密图的和顶点关系密切且能处理负权边的Floyd算法，以及采用贪心策略适用于稠密图和顶点关系密切不能处理负权边的Dijkstra算法
TIPS： Floyd算法虽然能处理负权边但是不能解决带有“负权回路”(负权环)，因为带有负权回路的图没有最短路径，因为总能找到比当前最小值更小的路径。因此最大路径也就不存在
-
网络延迟时间
我的题解：
思路:本题三种算法都可采用
1.Floyd算法(邻接矩阵)：核心是要求两个点的最短距离，可以尝试用第三个点进行周转，看能否在周转后是的这两个点的距离更短，若可以我们就更新当前这两个点的最短路径
class Solution { int INF = 0x3f3f3f3f; int n; int[][] arr; public int networkDelayTime(int[][] times, int _n, int k) { n = _n + 1; arr = new int[n][n]; for (int i = 1; i < n; i++) { for (int j = 1; j < n; j++) { arr[i][j] = arr[j][i] = i == j ? 0 : INF; } } for(int[] cur : times){ arr[cur[0]][cur[1]] = cur[2]; } floyd(arr); int max = 0; for (int i = 1; i < n; i++) { max = Math.max(arr[k][i], max); } return max == INF ? -1 : max; } //Floyd核心语句 void floyd(int[][] arr){ for (int k = 1; k < n; k++) { for (int i = 1; i < n; i++) { for (int j = 1; j < n; j++) { arr[i][j] = Math.min(arr[i][j], arr[i][k] + arr[k][j]); } } } } }2.Dijkstra算法(邻接矩阵)：核心思想是通过边来松弛一号顶带你到其他顶点的距离，采用贪心策略，每次都选择一个未访问的点，离1号顶点最近的点，来进行松弛操作。单源最短路径
class Solution { int K = 110, N = 110; int[][] w = new int[N][N]; boolean[] vis = new boolean[N]; int[] dis = new int[N]; int inf = 0x3f3f3f3f; /** * dijkstra 核心思想是通过边来松弛一号顶点到其他各顶点的距离 * @param times * @param _n * @param _k * @return */ public int networkDelayTime(int[][] times, int _n, int _k) { int n = _n + 1; int k = _k; //初始化邻接矩阵，主对角线上为0，其它为无穷 for (int i = 1; i < n; i++) { for (int j = 1; j < n; j++) { w[i][j] = w[j][i] = i == j ? 0 : inf; } } //用times进一步初始化边的权值 for(int[] i : times){ w[i[0]][i[1]] = i[2]; } //初始化dis，k节点未0，其他为inf Arrays.fill(dis, inf); dis[k] = 0; //Dijkstra核心语句 for (int i = 1; i < n; i++) { int t = 0, min = inf; //每次都选择一个离一号节点最近的点 for (int j = 1; j < n; j++) { if(!vis[j] && min > dis[j]) { min = dis[j]; t = j; } } //标记为已访问 vis[t] = true; //用该点的边去松弛1号顶点到其它顶点的距离 for(int j = 1; j < n; j++){ if(dis[j] > dis[t] + w[t][j]){ dis[j] = dis[t] + w[t][j]; } } } //若1号顶点到其它顶点存在有效路径，那么就返回这些路径中的最大值 int max = 0; for (int i = 1; i < n; i++) { max = Math.max(max, dis[i]); } return max > inf / 2 ? -1 : max; } }3.**Dijkstra + 最小堆 算法：**这里用最小堆进行优化每次选取一个
class Solution { int K = 110, N = 110; int[][] w = new int[N][N]; int[] dis = new int[N]; int inf = 0x3f3f3f3f; /** * dijkstra 核心思想是通过边来松弛一号顶点到其他各顶点的距离 * @param times * @param _n * @param _k * @return */ public int networkDelayTime(int[][] times, int _n, int _k) { int n = _n + 1; int k = _k; for (int i = 1; i < n; i++) { for (int j = 1; j < n; j++) { w[i][j] = w[j][i] = i == j ? 0 : inf; } } for(int[] i : times){ w[i[0]][i[1]] = i[2]; } Arrays.fill(dis, inf); //核心语句 //最小堆 PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(); dis[k] = 0; //将k号节点加入最小堆中 priorityQueue.add(k); //当队列不为空，就弹出当前节点 while(!priorityQueue.isEmpty()){ int t = priorityQueue.poll(); //松弛操作 //枚举每一个节点 for (int j = 1; j < n; j++) { //若t -> j之间存在边，使得dis[j] > dis[t] + w[t][j],我们就更新原点到j点的最短路径,并将该点加入队列中 if(w[t][j] < inf / 2 && dis[j] > dis[t] + w[t][j]){ dis[j] = dis[t] + w[t][j]; priorityQueue.add(j); } } } int max = 0; for (int i = 1; i < n; i++) { max = Math.max(max, dis[i]); } return max > inf / 2 ? -1 : max; } }4.BellmanFord算法:对所有边进行n-1次松弛操作
class Solution { int N = 110, M = 6010; int inf = -1; int[] u = new int[M], v = new int[M], w = new int[M]; int[] dis = new int[N]; public int networkDelayTime(int[][] ts, int _n, int _k) { int m = ts.length; int n = _n; int k = _k; for (int i = 1; i <= m; i++) { u[i] = ts[i - 1][0]; v[i] = ts[i - 1][1]; w[i] = ts[i - 1][2]; } Arrays.fill(dis, inf); dis[k] = 0; //核心语句 for (int i = 1; i < n; i++) { //枚举每条边 for (int j = 1; j <= m; j++) { //若当前原点到u[j]存在边 if(dis[u[j]] != inf){ //若原点到v[j]的距离以前不存在路径，我们就通过中间节点u[j]对v[j]到原点的距离进行松弛操作 if(dis[v[j]] == inf){ dis[v[j]] = dis[u[j]] + w[j]; //若存在路径，且松弛后的路径更短，就更新原点到v[j]的最短距离 }else{ dis[v[j]] = Math.min(dis[v[j]], dis[u[j]] + w[j]); } } } } int max = 0; for (int i = 1; i <= n; i++) { if(dis[i] == inf) return -1; max = Math.max(dis[i], max); } return max; } }5.BellmanFord算法 + 队列：这里可以用队列优化的原因是，若当前节点不在队列中，且通过本次松弛操作使得原点到目标节点的距离变短(可达)，则我们将当前节点加入队列中。这里实现时，我们可以用一个长度为n的名为vis的boolean类型数组进行标记当前节点是否在队列中，初始化时我们将节点k加入队列中，并标记vis[k] = true,在弹出时我们将vis[k]重新置为false，在松弛操作有效时，我们先判断vis[i]是否为false若时，我们就将节点i加入队列中
class Solution { /** * spfa算法 * @param times * @param n * @param k * @return */ int N = 110, M = 6010, inf = 0x3f3f3f3f; int[] dis = new int[N]; boolean[] vis = new boolean[N]; int[][] w = new int[N][N]; int n, k, m; public int networkDelayTime(int[][] times, int _n, int _k) { m = times.length; n = _n; k = _k; //构图 for (int i = 1; i <= n; i++) { for (int j = 1; j <= n ; j++) { w[i][j] = w[j][i] = i == j ? 0 : inf; } } for (int i = 0; i < m; i++) { w[times[i][0]][times[i][1]] = times[i][2]; } spfa(); //获取最大值 int max = 0; for (int i = 1; i <= n; i++) { max = Math.max(max, dis[i]); } return max > inf / 2 ? -1 : max; } //核心语句 void spfa(){ //初始化dis Arrays.fill(dis, inf); //标记原点，并将原点标记为已访问，加入队列中 dis[k] = 0; vis[k] = true; Queue<Integer> queue = new ArrayDeque<>(); queue.offer(k); while(!queue.isEmpty()){ int t = queue.poll(); vis[t] = false; //枚举该点的每条边 for (int i = 1; i <= n; i++) { //若原点和t节点之间边，且t节点到i节点之间存在边，且本次更新能使得原点到dis[i]之间的路径变短，我们就进行松弛操作 if(dis[t] < inf / 2 && w[t][i] < inf / 2 && dis[i] > dis[t] + w[t][i]){ dis[i] = dis[t] + w[t][i]; //若节点i不在队列中，我们就将节点i加入队列 if(!vis[i]){ queue.offer(i); vis[i] = true; } } } } } } -
787. K 站中转内最便宜的航班
我的题解：
思路:该题的思路可以是动态规划或者是使用BellmanFord算法
1.动态规划，第i个城市只能从第j个城市转移而来，而转移的次数t只能从t-1次转移而来
class Solution { int INF = 100000, N = 110; int[][] dp = new int[N][N]; /** * 状态转移方程：dp[t][i] = min(dp[t][i], dp[t-1][j] + cost) * 边界条件:dp[0][src] = 0 * @param n * @param flights * @param src * @param dst * @param k * @return */ public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) { int t = k + 1; for (int i = 0; i <= t; i++) { Arrays.fill(dp[i], INF); } //边界条件 dp[0][src] = 0; //状态转移 for (int c = 1; c <= t; c++) { for (int[] flight : flights) { int i = flight[1], j = flight[0], cost = flight[2]; dp[c][i] = Math.min(dp[c][i], dp[c - 1][j] + cost); } } int min = INF; for (int i = 0; i <= t; i++) { min = Math.min(min, dp[i][dst]); } return min == INF ? -1 : min; } }2.BellmanFord + 邻接矩阵
class Solution { int N = 110, INF = 0x3f3f3f3f; int[][] g = new int[N][N]; int[] dis = new int[N]; /** * BellmanFord * @param n * @param flights * @param src * @param dst * @param k * @return */ public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { g[i][j] = g[j][i] = i == j ? 0 : INF; } } for(int[] flight : flights){ int u = flight[0], v = flight[1], w = flight[2]; g[u][v] = w; } //t从0 ~ k次一共k+1次，代表从1 ~ k+1,i起始点，j终点，通过从i~j这条边不断对从src到j的路径进行松弛操作 Arrays.fill(dis, INF); dis[src] = 0; //外层控制松弛的次数 for (int t = 0; t < k + 1; t++) { //这里确保每次循环只会松弛一次 int[] c = dis.clone(); //若存在i -> j的路径且存在src到i的路径，且松弛后路径更短就进行松弛 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { dis[j] = Math.min(dis[j], c[i] + g[i][j]); } } } return dis[dst] == INF ? -1 : dis[dst]; } }3.BellmanFord(推荐)
class Solution { int N = 110, INF = 0x3f3f3f3f; int[] dis = new int[N]; /** * 不使用邻接矩阵或邻接表，这里直接使用flights中的边对dis从0~n的路径进行松弛操作,BellManFord算法的外层循环就是中转的次数 * @param n * @param flights * @param src * @param dst * @param k * @return */ public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) { Arrays.fill(dis, INF); dis[src] = 0; //外层控制松弛的次数 for (int i = 0; i < k + 1; i++) { //这里确保每次只松弛一次，同一层不会松弛多次 int[] c = dis.clone(); for (int[] flight : flights) { int u = flight[0], v = flight[1], w = flight[2]; dis[v] = Math.min(dis[v], c[u] + w); } } return dis[dst] > INF / 2 ? -1 : dis[dst]; } } -
1928. 规定时间内到达终点的最小花费
我的题解：
思路:本题有两个约束，时间约束和最短路径约束，可以用动态规划来解决，特别需要注意的是这里因为路径是无向的，因此需要双向状态转移
动态规划问题的核心是找出边界条件和状态转移方程
边界条件:
d
p
[
i
]
[
j
]
=
p
a
s
s
i
n
g
F
e
e
s
[
0
]
(
i
=
0
,
j
=
0
)
dp[i][j] = passingFees[0] (i = 0, j = 0)
dp[i][j]=passingFees[0](i=0,j=0)
d
p
[
i
]
[
j
]
=
I
N
F
(
i
!
=
0
，
j
!
=
0
)
dp[i][j] = INF (i != 0 ，j != 0)
dp[i][j]=INF(i!=0，j!=0)
状态转移方程:
d
p
[
t
]
[
i
]
=
m
i
n
(
d
p
[
t
]
[
i
]
,
d
p
[
t
−
w
]
[
j
]
+
p
a
s
s
i
n
g
F
e
e
s
[
i
]
)
(
t
>
=
w
)
dp[t][i] = min(dp[t][i], dp[t - w][j] + passingFees[i]) (t >= w)
dp[t][i]=min(dp[t][i],dp[t−w][j]+passingFees[i])(t>=w)
d
p
[
t
]
[
j
]
=
m
i
n
(
d
p
[
t
]
[
j
]
,
d
p
[
t
−
w
]
[
i
]
+
p
a
s
s
i
n
g
F
e
e
s
[
j
]
)
(
t
>
=
w
)
dp[t][j] = min(dp[t][j], dp[t - w][i] + passingFees[j]) (t >= w)
dp[t][j]=min(dp[t][j],dp[t−w][i]+passingFees[j])(t>=w)
class Solution { int INF = 0x3f3f3f3f; int T = 1010, N = 1010; int[][] dp = new int[T][N]; /** * 边界条件:dp[0][0] = passingFees[0] * 状态转移方程:dp[t][j] = min(dp[t][j], dp[t - w][i] + passingFees[j]) * dp[t][i] = min(dp[t][i], dp[t - w][j] + passingFees[i]) * @param maxTime * @param edges * @param passingFees * @return */ public int minCost(int maxTime, int[][] edges, int[] passingFees) { int n = passingFees.length; for (int i = 0; i <= maxTime; i++) { Arrays.fill(dp[i], INF); } //边界条件 dp[0][0] = passingFees[0]; //状态转移 for (int t = 1; t <= maxTime; t++) { for(int[] edge : edges){ int i = edge[0], j = edge[1], w = edge[2]; //双向 if(t - w >= 0){ dp[t][i] = Math.min(dp[t][i], dp[t - w][j] + passingFees[i]); dp[t][j] = Math.min(dp[t][j], dp[t - w][i] + passingFees[j]); } } } int min = INF; for (int t = 1; t <= maxTime; t++) { min = Math.min(min, dp[t][n - 1]); } return min > INF / 2 ? -1 : min; } } -
1334. 阈值距离内邻居最少的城市
我的题解：
思路:多源最短路径考虑用floyd算法解决,时间复杂度O(N3),空间复杂度O(N2)
//初始化参数 int N = 110, INF = 0x3f3f3f3f; int[][] g = new int[N][N]; int[] counts = new int[N]; public int findTheCity(int n, int[][] edges, int distanceThreshold) { //构图 for (int i = 0; i < n; i++) { Arrays.fill(g[i], INF);//不存在自己到自己的边 } for(int[] edge : edges){ int u = edge[0], v = edge[1], w = edge[2]; g[u][v] = g[v][u] = w;//无向图双向赋值 } //floyd算法 for (int k = 0; k < n; k++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if(j != i && g[i][k] < INF / 2 && g[k][j] < INF / 2 && g[i][k] + g[k][j] < g[i][j]){//不存在环，因此i，j不能相同 g[i][j] = g[i][k] + g[k][j]; } } } } //对小于distance的边进行计数 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if(g[i][j] <= distanceThreshold) counts[i]++; } } //找出点最少的边，且索引最大 int idx = 0, min = INF; for (int i = 0; i < n; i++) { if(counts[i] <= min){ min = counts[i]; idx = i; } } return idx; } -
1368. 使网格图至少有一条有效路径的最小代价
我的题解：
思路:可以将每个格子看成一个点，对于一个点与它相邻的点有一条无向边相连，其中grid(i)(j)中的数字从1~4对应着四个方向，若与扩展的方向相同则该边的权重为0，反之为1，这样一来该题同样可以看成最短路径问题(单源最短路径)。
在这里介绍两种方法：dijsktra算法和0-1BFS算法
dijkstra的核心思路是每一次取一个离原点最近且未访问的点，用该点的边对原点到其它的的距离进行松弛操作，使得原点到其它点的距离从不可达变为可达或距离缩短(开销变小)
0-1BFS的核心思路是若此次松弛有效(使得原点到其它点的距离从不可达变为可达或距离缩短(开销变小))，且边的权值只存在两种可能0或1，那么将权值为0的加到双向队列的头结点前，若为1则加到双向队列的尾结点后
1.Dijkstra:
import java.util.Arrays; import java.util.Comparator; import java.util.PriorityQueue; public class Test1 { int[] dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0}; final int INF = 0x3f3f3f3f; /** * 思路：最短路径(这里的最短路径指的是最小的次数),因此仍然可以使用dijkstra算法 * 这里使用优先队列优化后的dijkstra算法 * step1:初始化count为INF，并初始化count[0][0]为0，vis[0][0]为true,将0,0点加入优先队列中 * step2:若优先队列不为空，就弹出队首的元素，表示离远点最近的元素，然后用该点的四个方向的边，对相邻的点到原点的距离进行松弛操作 * step3:返回count[m-1][n-1] * @param grid * @return */ public int minCost(int[][] grid) { //step1 int m = grid.length, n = grid[0].length; int[][] count = new int[m][n]; boolean[][] vis = new boolean[m][n]; for (int i = 0; i < m; i++) { Arrays.fill(count[i], INF); } count[0][0] = 0; PriorityQueue<int[]> priorityQueue = new PriorityQueue<int[]>(Comparator.comparingInt(a -> a[1]) ); priorityQueue.offer(new int[] {0, 0}); //step2 while(!priorityQueue.isEmpty()){ int[] cur = priorityQueue.poll(); int x = cur[0] / n, y = cur[0] % n; //若该点已访问则跳过，这里同一个点可能更新多次 if(vis[x][y]) continue; vis[x][y] = true; for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; //路径不重复，不需要确保点未访问 if(nx >= 0 && nx < m && ny >= 0 && ny < n){ int cnt = grid[x][y] == i + 1 ? 0 : 1; if(count[nx][ny] > count[x][y] + cnt){ count[nx][ny] = count[x][y] + cnt; priorityQueue.offer(new int[] {nx * n + ny, count[nx][ny]}); } } } } //step3 return count[m - 1][n - 1]; } }2.0-1BFS
import java.util.Arrays; import java.util.Deque; import java.util.LinkedList; public class Test2 { /** * 思路:0-1BFS * 步骤: * 1.初始化cost，将初始元素加入队列中 * 2.当队列不为空，尝试在四个方向上进行扩展，若可以扩展，则记录此时的代价c，若此次松弛操作有效则更新扩展点的cost与此同时，根据c为0还是为1将 * 扩展点加入队列头结点还是尾节点位置 * 3.最后返回cost[m-1][n-1] * @param grid * @return */ final int INF = 0x3f3f3f3f; int[] dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0}; public int minCost(int[][] grid) { //step1 int m = grid.length, n = grid[0].length; int[][] cost = new int[m][n]; for (int i = 0; i < m; i++) { Arrays.fill(cost[i], INF); } cost[0][0] = 0; Deque<Integer> deque = new LinkedList<>(); deque.offer(0); //step2 while(!deque.isEmpty()){ int cur = deque.poll(); int x = cur / n, y = cur % n; for (int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if(nx >= 0 && nx < m && ny >= 0 && ny < n){ int c = grid[x][y] == i + 1 ? 0 : 1; if(cost[nx][ny] > cost[x][y] + c){ cost[nx][ny] = cost[x][y] + c; //核心 if(c == 0){ deque.offerFirst(nx * n + ny); }else{ deque.offer(nx * n + ny); } } } } } //step3 return cost[m - 1][n - 1]; } } -
1514. 概率最大的路径
我的题解：
思路:本题同样是最短路的问题，可以这样考虑最短路的核心思想是找到一条最优解的路径，这里的最优解路径指的是概率最大的路径，因此我们同样可以使用单源最短路径算法Dijkstra、BellmanFord或SPFA来解决
TIPS:注意这里是无向图因此在构图的时候需要建立双向路径
1.Dijkstra + 数组
/** * 思路:该题同样是最短路径的思想，只不过这里的最短路径换成了最大的乘积，核心思想也是一样的，在这里INF对应的值是-1，dis[0]=1,其它为INF，单原最短路径 * 考虑用Dijkstra算法或BellmanFord算法,这里我们用邻接表来实现 * 步骤: * 1.构图，初始化dis,vis * 2.Dijkstra * 3.根据dis[end]的值返回结果 * @param n * @param edges * @param succProb * @param start * @param end * @return */ final int INF = -1; public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) { //step1 int m = edges.length; double[] dis = new double[n]; boolean[] vis = new boolean[n]; List<List<double[]>> g = new ArrayList<>(); for (int i = 0; i < n; i++) { g.add(new ArrayList<>()); } //无向图双向连接 for (int i = 0; i < m; i++) { int u = edges[i][0], v = edges[i][1]; g.get(u).add(new double[] {v, succProb[i]}); g.get(v).add(new double[] {u, succProb[i]}); } Arrays.fill(dis, INF); dis[start] = 1d; //step2 PriorityQueue<double[]> pq = new PriorityQueue<>(new Comparator<double[]>() { @Override public int compare(double[] o1, double[] o2) { if(o2[1] > o1[1]) return 1; else return -1; } });//这里需要每次获取一个最大的值 pq.offer(new double[] {start, 1}); while(!pq.isEmpty()){ double[] cur = pq.poll(); int u = (int) cur[0]; if(vis[u]) continue;//若该点已访问过则跳过 vis[u] = true;//标记该点为已访问 for (int i = 0; i < g.get(u).size(); i++) { int v = (int) g.get(u).get(i)[0]; double w = g.get(u).get(i)[1]; if(dis[v] < dis[u] * w){//松弛操作，这里是选最大的值 dis[v] = dis[u] * w; pq.offer(new double[]{v, dis[v]}); } } } System.out.println(Arrays.toString(dis)); //step3 return dis[end] == -1 ? 0 : dis[end]; } }2.Dijkstra + 类
class Solution { final int INF = -1; public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) { //step1 int m = edges.length; double[] dis = new double[n]; boolean[] vis = new boolean[n]; List<List<Pair>> g = new ArrayList<>(); for (int i = 0; i < n; i++) { g.add(new ArrayList<>()); } //无向图双向可达 for (int i = 0; i < m; i++) { int u = edges[i][0], v = edges[i][1]; g.get(u).add(new Pair(v, succProb[i])); g.get(v).add(new Pair(u, succProb[i])); } Arrays.fill(dis, INF); dis[start] = 1; //step2 PriorityQueue<Pair> pq = new PriorityQueue<Pair>(new Comparator<Pair>() { @Override public int compare(Pair a, Pair b) { // TODO 自动生成的方法存根 if(b.w > a.w) return 1; else return -1; } });//这里需要每次获取一个最大的值 pq.offer(new Pair(start, 1)); while(!pq.isEmpty()){ Pair cur = pq.poll(); int u = cur.u; if(vis[u]) continue;//若该点已访问过则跳过 vis[u] = true;//标记该点为已访问 for (int i = 0; i < g.get(u).size(); i++) { int v = g.get(u).get(i).u; double w = g.get(u).get(i).w; if(dis[v] < dis[u] * w){//松弛操作，这里是选最大的值 dis[v] = dis[u] * w; pq.offer(new Pair(v, dis[v])); } } } //step3 return dis[end] == -1 ? 0 : dis[end]; } class Pair{ int u; double w; public Pair(int _u, double _w) { u = _u; w = _w; } } }3.BellmanFord + 类 (无法通过评测，只供参考)
/** * BellmanFord算法 * 无向图-最短路径-类实现 * 步骤: * 1.初始化dis,vis * 2.调用BellmanFord算法解决，优先选择路径大的 * 3.根据dis[end]的值决定最终的返回值 * 提示:因为单独提供了所有边的信息，所以这里不需要构图，但是在进行松弛操作时需要双向松弛操作 * @param n * @param edges * @param succProb * @param start * @param end * @return */ final int INF = -1; public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) { //step1 int m = edges.length; double[] dis = new double[n]; Arrays.fill(dis, INF); dis[start] = 1; //step2 for (int i = 0; i < n - 1; i++) { for (int j = 0; j < m; j++) { int u = edges[j][0], v = edges[j][1]; double w = succProb[j]; //双向松弛 if(dis[u] >= 0 && dis[v] < dis[u] * w){ dis[v] = dis[u] * w; } if(dis[v] >= 0 && dis[u] < dis[v] * w){ dis[u] = dis[v] * w; } } } //step3 return dis[end] == -1 ? 0 : dis[end]; } }4.SPFA + 邻接表 + 类 (最佳)
/** * SPFA + 邻接表 * 步骤: * 1.构图-无向图双向连接，初始化dis,vis和queue * 2.调用SPFA算法进行松弛操作 * 3.根据dis[end]的值决定返回值 * @param n * @param edges * @param succProb * @param start * @param end * @return */ final int INF = -1; public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) { //step1 int m = edges.length; boolean[] vis = new boolean[n]; double[] dis = new double[n]; List<List<Pair>> g = new ArrayList<>(); for (int i = 0; i < n; i++) { g.add(new ArrayList<>()); } for (int i = 0; i < m; i++) { int u = edges[i][0], v = edges[i][1]; double w = succProb[i]; g.get(u).add(new Pair(v, w)); g.get(v).add(new Pair(u, w)); } Arrays.fill(dis, INF); dis[start] = 1; vis[start] = true; Queue<Integer> queue = new ArrayDeque<>(); queue.offer(start); //step2:核心 while(!queue.isEmpty()){ int u = queue.poll(); vis[u] = false; for (int i = 0; i < g.get(u).size(); i++) { int v = g.get(u).get(i).u; double w = g.get(u).get(i).w; //松弛 if(dis[v] < dis[u] * w){ dis[v] = dis[u] * w; if(!vis[v]) { vis[v] = true; queue.offer(v); } } } } //step3 return dis[end] == INF ? 0 : dis[end]; } class Pair{ int u; double w; public Pair(int _u, double _w) { u = _u; w = _w; } } -
1976. 到达目的地的方案数
我的题解：
思路:无向图-最短路径-邻接表-dp，该题可以考虑用Dijkstra算法解决，在此基础上需要维护一个计数器数组dp
动态规划
边界条件:dp[0] = 1
递推公式:
i
f
(
d
i
s
[
v
]
>
d
i
s
[
u
]
+
w
)
d
p
[
v
]
=
d
p
[
u
]
if(dis[v] > dis[u] + w) dp[v] = dp[u]
if(dis[v]>dis[u]+w)dp[v]=dp[u]
i
f
(
d
i
s
[
v
]
=
d
i
s
[
u
]
+
w
)
d
p
[
v
]
=
d
p
[
u
]
+
d
p
[
v
]
if(dis[v] = dis[u] + w) dp[v] = dp[u] + dp[v]
if(dis[v]=dis[u]+w)dp[v]=dp[u]+dp[v]
步骤:
1.构图，初始化dis,vis和counts
2.调用dijkstra来求最短路并对根据条件求出dp[i]
3.返回counts[n-1]**TIPS:**这里存储路径长度时需要用long类型，dp中的值在相加时需要进行取模操作
class Solution { long INF = Long.MAX_VALUE >> 2; int MOD = (int) (1e9 + 7); public int countPaths(int n, int[][] roads) { int m = roads.length; //step1 List<List<Pair>> g = new ArrayList<>(); for (int i = 0; i < n; i++) { g.add(new ArrayList<>()); } for (int i = 0; i < m; i++) { int u = roads[i][0], v = roads[i][1], w = roads[i][2]; g.get(u).add(new Pair(v, w)); g.get(v).add(new Pair(u, w)); } long[] dis = new long[n]; int[] dp = new int[n]; boolean[] vis = new boolean[n]; Arrays.fill(dis, INF); dis[0] = 0; //边界条件 dp[0] = 1; PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[1])); pq.offer(new long[] {0, 0}); //step2 while(!pq.isEmpty()){ long[] cur = pq.poll(); int u = (int) cur[0]; if(vis[u]) continue; vis[u] = true; for (int i = 0; i < g.get(u).size(); i++) { int v = g.get(u).get(i).u, w = g.get(u).get(i).w; //计数 if(dis[u] < INF && dis[v] == dis[u] + w){ dp[v] += dp[u]; dp[v] %= MOD; } //覆盖 else if(dis[u] < INF && dis[v] > dis[u] + w){ dp[v] = dp[u]; dis[v] = dis[u] + w; pq.offer(new long[]{v, dis[v]}); } } } //step3 return dp[n - 1]; } class Pair{ int u; int w; public Pair(int u, int w) { this.u = u; this.w = w; } } }