最短路算法模板

最短路算法有很多種，包括Dijkstra算法、Bellman-Ford算法、A*算法等。這裡提供一個Dijkstra算法的模板，用於在有向圖中找到從一個頂點到其他所有頂點的最短路徑。

#include <vector>
#include <queue>
#include <utility>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

struct Graph {
    std::vector<std::vector<int>> adjList;
    int V; // 頂點數

    Graph(int V) : V(V) {
        adjList.resize(V);
    }

    void addEdge(int src, int dest, int weight) {
        adjList[src].push_back({dest, weight});
    }
};

struct Edge {
    int dest;
    int weight;
};

struct Compare {
    bool operator()(const Edge& a, const Edge& b) const {
        return a.weight > b.weight;
    }
};

class DisjointSet {
public:
    DisjointSet(int n) : parent(n, -1), rank(n) {}

    int find(int i) {
        if (parent[i] < 0)
            return i;
        else
            return parent[i] = find(parent[i]);
    }

    void unionSet(int x, int y) {
        int xRoot = find(x);
        int yRoot = find(y);

        if (xRoot == yRoot)
            return;

        if (rank[xRoot] < rank[yRoot]) {
            parent[xRoot] = yRoot;
        } else if (rank[yRoot] < rank[xRoot]) {
            parent[yRoot] = xRoot;
        } else {
            parent[yRoot] = xRoot;
            rank[xRoot]++;
        }
    }

private:
    std::vector<int> parent;
    std::vector<int> rank;
};

class PriorityQueue {
public:
    PriorityQueue(int capacity) : maxSize(capacity), size(0) {
        pq.resize(capacity);
    }

    void push(const Edge& e) {
        pq[size++] = e;
        if (size > maxSize / 2) {
            std::make_heap(pq.begin(), pq.begin() + size, Compare());
        }
    }

    Edge pop() {
        if (size == 0)
            return Edge();

        std::pop_heap(pq.begin(), pq.begin() + size, Compare());
        Edge res = pq[size - 1];
        pq.pop_back();
        size--;
        return res;
    }

private:
    const int maxSize;
    int size;
    std::vector<Edge> pq;
};

void dijkstra(Graph& graph, int src) {
    std::vector<int> dist(graph.V, INT_MAX);
    std::vector<bool> visited(graph.V, false);
    dist[src] = 0;

    PriorityQueue pq(graph.V);
    pq.push({src, 0});

    while (!pq.empty()) {
        Edge edge = pq.pop();
        int u = edge.dest;
        if (dist[u] != INT_MAX)
            continue;

        visited[u] = true;
        for (auto& neighbor : graph.adjList[u]) {
            int v = neighbor.dest;
            int weight = neighbor.weight;
            if (dist[v] > dist[u] + weight) {
                dist[v] = dist[u] + weight;
                pq.push({v, dist[v]});
            }
        }
    }

    for (int i = 0; i < graph.V; i++) {
        std::cout << dist[i] << " ";
    }
    std::cout << std::endl;
}

int main() {
    int V, E;
    std::cin >> V >> E;
    Graph graph(V);

    for (int i = 0; i < E; i++) {
        int src, dest, weight;
        std::cin >> src >> dest >> weight;
        graph.addEdge(src - 1, dest - 1, weight);
    }

    dijkstra(graph, 0);
    return 0;
}

這個模板使用了一個優先佇列來維護一個最小堆，用於存儲未訪問的頂點及其距離。它還使用了一個DisjointSet數據結構來維護併查集，用於判斷兩個頂點是否在同一連通分量中。在實際套用中，你可能需要根據具體問題調整算法和數據結構。