Shortest Path

Floyd Warshall

Link

• 尋找點對點之間的最短距離

• 更新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

Link

• 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 = 7

public 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.

Explain

1. 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))