Shortest Path
Floyd Warshall
尋找點對點之間的最短距離
更新v次edge的情況
Time O(n^3)
package graph;
import com.sun.tools.doclets.formats.html.SourceToHTMLConverter;
import java.util.*;
public class floyd_warshall {
private void fw(int v, int[][] edges){
int inf = (int)1e8;
// init distance matrix
int[][] matrix = new int[v][v];
for(int i=0; i<v; i++){
for(int j=0; j<v; j++){
if(i==j) matrix[i][j]=0;
else matrix[i][j] = inf;
}
}
// read the edge to matrix
for(int[] e: edges){
matrix[e[0]][e[1]] = e[2];
}
// Floyd Warshall Algo
for(int k=0; k<v; k++){
for(int i=0; i<v; i++){
for(int j=0; j<v; j++){
if(matrix[i][j] > matrix[i][k] + matrix[k][j]){
matrix[i][j] = matrix[i][k] + matrix[k][j];
}
}
}
}
// print matrix
StringBuilder sb = new StringBuilder();
for(int[] row: matrix){
for(int n: row){
sb.append(n).append(",");
}
sb.append("\n");
}
System.out.println(sb.toString());
}
public static void main(String[] args) {
floyd_warshall f = new floyd_warshall();
int[][] e = new int[][]{
{0,1,2},
{0,2,6},
{0,3,4},
{1,2,3},
{2,0,7},
{2,3,1},
{3,0,5},
{3,2,12}
};
f.fw(4, e);
}
}Dijkstra
Greedy, 每次尋找neighbor dist最短的vertex
weight不能是負數
Time O(E + VlogV)
A visited set, a minHeap<[node][distance to start]>
Heap會優先更新距離短的，使vertex 更新必定是最短距離
package graph;
import java.util.*;
public class dijkstra {
private void algo(int num, int[][] edges, int start){
int distance[] = new int[num];
// int[0] is vertex, int[1] is distance
Queue<int[]> heap = new PriorityQueue<>((a,b)->a[1]-b[1]);
// init distance matrix
int[][] matrix = new int[num][num];
// read the edge to matrix
for(int[] e: edges) {
matrix[e[0]][e[1]] = e[2];
}
// init distance[]
Arrays.fill(distance, Integer.MAX_VALUE);
distance[start] = 0;
heap.add(new int[]{start, 0});
// Dijkstra Algo
while(!heap.isEmpty()){
int[] vertex_u = heap.poll();
int u = vertex_u[0];
// loop the neighbors
for(int v=0; v<num; v++){
if(matrix[u][v] != 0){
if(distance[v] > distance[u] + matrix[u][v]){
distance[v] = distance[u] + matrix[u][v];
}
heap.add(new int[]{v, distance[v]});
}
}
}
// print distance[]
for(int dist: distance){
System.out.println(dist);
}
}
public static void main(String[] args) {
dijkstra d = new dijkstra();
int[][] edges = new int[][]{
{0,1,1},
{0,2,12},
{1,2,9},
{1,3,3},
{2,4,5},
{3,2,4},
{3,4,13},
{3,5,15},
{4,5,4}
};
d.algo(6,edges,0);
// [0, 1, 8, 4, 13, 17]
}
}787. Cheapest Flights Within K Stops
There are n cities connected by m flights. Each fight starts from city u and arrives at v with a price w.
Now given all the cities and fights, together with starting city src and the destination dst, your task is to find the cheapest price from src to dst with up to k stops. If there is no such route, output -1.
maintain cost and stop array
遇到 dst 即退出
遇到 stop >= K+1 即拋棄 continue
update cost[v] if curCost + matrix[u][v] is less
update stop[v] if stop+1 is less
return cost[v] and check if valid
[[0,1,5],[1,2,5],[0,3,2],[3,1,2],[1,4,1],[4,2,1]]
0
2
2
answer = 7public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
int[][] matrix = new int[n][n];
// init matrix
for(int[] flight: flights){
matrix[flight[0]][flight[1]] = flight[2];
}
// init cost[]
int[] costs = new int[n];
Arrays.fill(costs, Integer.MAX_VALUE);
costs[src] = 0;
// init stop[]
int[] stops = new int[n];
Arrays.fill(stops, Integer.MAX_VALUE);
// int[0]=vertex, int[1]=number of stops, int[2]=cost
Queue<int[]> heap = new PriorityQueue<>((a,b) -> a[2] - b[2]);
heap.add(new int[]{src, 0, 0});
while(!heap.isEmpty()){
int[] cur = heap.poll();
int u = cur[0], curStop = cur[1], curCost= cur[2];
if(u == dst) return curCost;
if(curStop == K+1) continue;
for(int v=0; v<n; v++){
if(matrix[u][v] != 0){
int newCost = curCost+matrix[u][v];
int newStop = curStop+1;
// 更新到 v 點的 lowest cost
if(costs[v] > newCost){
heap.add(new int[]{v, newStop, newCost});
costs[v] = newCost;
}
// 加上雖然cost較大，但轉機次數較少的vertax
else if(stops[v] > newStop){
heap.add(new int[]{v, newStop, newCost});
stops[v] = newStop;
}
}
}
}
return costs[dst]==Integer.MAX_VALUE ? -1: costs[dst];
}1102. Path With Maximum Minimum Value
Given a matrix of integers A with R rows and C columns, find the maximum score of a path starting at [0,0] and ending at [R-1,C-1].
The score of a path is the minimum value in that path. For example, the value of the path 8 → 4 → 5 → 9 is 4.
Local Greedy, 從四個方向找到 local min然後從maxHeap選擇max延伸
def maximumMinimumPath(self, A: List[List[int]]) -> int:
m, n = len(A), len(A[0])
seen = set()
maxHeap = [(-A[0][0], 0, 0)]
heapify(maxHeap)
while maxHeap:
val, i, j = heappop(maxHeap)
if (i, j) == (m-1, n-1): return -val
# seen.add((i, j)) 在這裡會TLE
for dy, dx in ((0, 1), (1, 0), (0, -1), (-1, 0)):
y = i + dy
x = j + dx
if not (0 <= y < m and 0 <= x < n and (y, x) not in seen): continue
# 這邊是要比較cur and new 哪個比較小
heappush(maxHeap, (max(val, -A[y][x]), y, x))
seen.add((y ,x)) # 在這會pass
# if A has only 1 element
return A[0][0]778. Swim in Rising Water
Input: [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]
Output: 16
Explanation:
0 1 2 3 4
24 23 22 21 5
12 13 14 15 16
11 17 18 19 20
10 9 8 7 6
The final route is marked in bold.
We need to wait until time 16 so that (0, 0) and (4, 4) are connected."""
Dijkstra: 每次尋找regional min
並且紀錄路線中出現的max
"""
from heapq import *
class Solution:
def swimInWater(self, grid: List[List[int]]) -> int:
n = len(grid)
heap = [(grid[0][0], 0, 0)]
max_t = 0
seen = set()
while heap:
val, i, j = heappop(heap)
max_t = max(max_t, val)
if (i, j) == (n-1, n-1): return max_t
for dy, dx in ((0,1), (1,0), (0,-1), (-1,0)):
y = i + dy
x = j + dx
if not(0<=y<n and 0<=x<n and (y,x) not in seen): continue
heappush(heap, (grid[y][x], y, x))
seen.add((y, x))Last updated
Was this helpful?