1382:最短路spfa

SPFA（Shortest Path Faster Algorithm）是一種用於尋找有向圖中單源點到所有其他頂點的最短路徑的算法。它基於Bellman-Ford算法，但通過維護一個佇列來最佳化路徑搜尋過程，從而減少了時間複雜度。

下面是一個簡單的SPFA算法的偽代碼實現：

function SPFA(graph, src):
    distTo[src] = 0
    for each vertex v in graph:
        distTo[v] = infinity
    queue = createQueue()
    queue.enqueue(src)
    while queue is not empty:
        vertex u = queue.dequeue()
        for each neighbor v of u:
            if distTo[v] > distTo[u] + weight(u, v):
                distTo[v] = distTo[u] + weight(u, v)
                predecessor[v] = u
                enqueue(v)
    return distTo

在這個偽代碼中，graph 是一個有向圖的表示，src 是我們要尋找最短路徑的源點，distTo 是一個數組，其中distTo[v]表示從源點 src 到頂點 v 的最短路徑的距離，predecessor 是一個數組，其中 predecessor[v] 表示 v 的父節點（即最短路徑上的上一個節點）。

weight(u, v) 表示從頂點 u 到頂點 v 的邊的權重。

createQueue() 函式創建一個佇列，enqueue(v) 函式將頂點 v 加入佇列，dequeue() 函式從佇列中刪除頂點。

在實際套用中，SPFA算法通常用於改進Bellman-Ford算法，因為它可以在某些情況下更快地找到最短路徑。然而，SPFA算法並不是對所有圖都能保證最優的時間複雜度，它的時間複雜度取決於圖中邊的數量和邊的分布情況。

對於有負權邊的圖，SPFA算法可能會陷入循環，無法找到最短路徑。因此，在使用SPFA算法時，需要確保圖中沒有負權迴路。

如果你想用代碼實現SPFA算法，可以使用C++、Java、Python等程式語言。以下是一個簡單的C++實現：

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct Vertex {
    int id;
    vector<int> edges;
};

struct Graph {
    int V;
    vector<Vertex> *vertices;
};

void addEdge(Graph *graph, int src, int dest, int weight) {
    graph->vertices[src].edges.push_back(dest);
    graph->vertices[dest].edges.push_back(src);
}

void SPFA(Graph *graph, int src) {
    int V = graph->V;
    vector<int> dist(V, INT_MAX);
    dist[src] = 0;
    queue<int> q;
    q.push(src);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = 0; i < graph->vertices[u].edges.size(); ++i) {
            int v = graph->vertices[u].edges[i];
            if (dist[v] > dist[u] + graph->vertices[u].weights[i]) {
                dist[v] = dist[u] + graph->vertices[u].weights[i];
                q.push(v);
            }
        }
    }
}

int main() {
    int V, E;
    cin >> V >> E;
    Graph *graph = new Graph();
    graph->V = V;
    graph->vertices = new vector<Vertex>[V];
    for (int i = 0; i < E; ++i) {
        int src, dest, weight;
        cin >> src >> dest >> weight;
        addEdge(graph, src, dest, weight);
    }
    SPFA(graph, 0);
    for (int i = 0; i < V; ++i) {
        cout << "Vertex " << i << " -> " << dist[i] << endl;
    }
    return 0;
}

請注意，這個代碼只是一個簡單的實現，實際套用中可能需要根據具體情況進行調整。