Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Leetcode 2642. Design Graph With Shortest Path Calculator #238

Open
Woodyiiiiiii opened this issue Apr 16, 2023 · 0 comments
Open

Leetcode 2642. Design Graph With Shortest Path Calculator #238

Woodyiiiiiii opened this issue Apr 16, 2023 · 0 comments

Comments

@Woodyiiiiiii
Copy link
Owner

模版题:求有向权值图中某个点到另一个点的最短路径。

1、Dijkstra

第一种方法就是用堆优化。用dist一维数组表示start起点到i点的最短距离,用最小堆记录下一个结点和权值:

class Graph {

    int n;
    Map<Integer, List<int[]>> adjList;

    public Graph(int n, int[][] edges) {
        this.n = n;
        adjList = new HashMap<>();
        for (int i = 0; i < n; i++) {
            adjList.put(i, new ArrayList<>());
        }
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            adjList.get(u).add(new int[]{v, w});
        }
    }

    public void addEdge(int[] edge) {
        int u = edge[0], v = edge[1], w = edge[2];
        adjList.get(u).add(new int[]{v, w});
    }

    public int shortestPath(int node1, int node2) {
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[node1] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        pq.add(new int[]{node1, 0});
        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int u = curr[0], d = curr[1];
            if (u == node2) {
                return dist[u];
            }
            for (int[] edge : adjList.get(u)) {
                int v = edge[0], w = edge[1];
                if (dist[v] > dist[u] + w) {
                    dist[v] = dist[u] + w;
                    pq.add(new int[]{v, dist[v]});
                }
            }
        }
        return -1;
    }
}

/**
 * Your Graph object will be instantiated and called as such:
 * Graph obj = new Graph(n, edges);
 * obj.addEdge(edge);
 * int param_2 = obj.shortestPath(node1,node2);
 */

另一种Dijkstra是设立访问数组,遍历所有结点,寻找最小的未被访问的dist,然后找到下一个结点。可以用数学归纳法证明遍历过的结点已经是最小值了。

class Graph {

    int n;
    Map<Integer, List<int[]>> adjList;

    public Graph(int n, int[][] edges) {
        this.n = n;
        adjList = new HashMap<>();
        for (int i = 0; i < n; i++) {
            adjList.put(i, new ArrayList<>());
        }
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            adjList.get(u).add(new int[]{v, w});
        }
    }

    public void addEdge(int[] edge) {
        int u = edge[0], v = edge[1], w = edge[2];
        adjList.get(u).add(new int[]{v, w});
    }

    public int shortestPath(int node1, int node2) {
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[node1] = 0;
        boolean[] v = new boolean[n];
        for (;;) {
            int x = -1;
            for (int i = 0; i < n; ++i) {
                if (!v[i] && (x < 0 || dist[i] < dist[x])) {
                    x = i;
                }
            }
            if (x < 0 || dist[x] == Integer.MAX_VALUE) {
                return -1;
            }
            if (x == node2) {
                return dist[node2];
            }
            v[x] = true;
            if (!adjList.containsKey(x)) {
                continue;
            }
            for (int[] next : adjList.get(x)) {
                dist[next[0]] = Math.min(dist[next[0]], dist[x] + next[1]);
            }
        }
    }
}

/**
 * Your Graph object will be instantiated and called as such:
 * Graph obj = new Graph(n, edges);
 * obj.addEdge(edge);
 * int param_2 = obj.shortestPath(node1,node2);
 */

时间复杂度O(qn^2)。

2、floyd
看详解。


Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant