倒數第二天~~

路徑(Path)

路徑(Path)是指圖中的一個序列，其中連接相鄰節點的邊構成了一條路徑。路徑可以用來表示從一個節點到另一個節點的過程，並通常用來解決許多不同的問題，例如尋找兩個節點之間的路徑、檢測圖中是否存在特定類型的路徑等。

最短路徑（Shortest Path）

其中，最短路徑（Shortest Path）問題是圖論中一個常見的挑戰，其目標是找到圖中兩個節點之間的最短路徑。這個最短路徑可以按不同標準來衡量，如權重最小、權重最大、或者經過的邊或節點數最少等。

最長路徑(Longest Path)

最長路徑問題是最短路徑問題的一個變體。在最長路徑問題中，你的目標是找到圖中兩個節點之間的最長路徑，而這個最長路徑是通過給每條邊的權重取負值來找到的。換句話說，最長路徑問題可以轉化為一個最短路徑問題，只需將所有邊的權重取相反數，然後使用最短路徑演算法來找到最短路徑，即可得到最長路徑。

相關演算法

以最短路徑問題為例，有幾種相關的演算法可供選擇，以應對不同情境：

• Dijkstra's Algorithm：找到單一源節點到圖中所有其他節點的最短路徑。它每次選擇最短路徑的節點進行擴展。
• Bellman-Ford Algorithm：處理帶有負權重邊的圖，並找到單一源節點到圖中所有其他節點的最短路徑。

這些演算法提供了不同的方法，可根據具體問題的性質和圖的特點來選擇適當的解決方案。最短路徑問題在路線規劃、網絡優化、通信網絡等領域有廣泛的應用。

Dijkstra's Algorithm

具體步驟如下：

1. 初始化：創建一個數組或列表，用於存儲每個節點到源節點的目前已知最短路徑估計值。將源節點的最短路徑設置為0，其他節點的最短路徑設置為無窮大。同時，建立一個集合用於跟蹤已經找到最短路徑的節點，初始時為空。
2. 選擇節點：從尚未處理的節點中選擇一個節點，該節點的最短路徑估計值是目前已知最小的。
3. 鬆弛邊：對於選中的節點，遍歷它的所有鄰接節點。對於每個鄰接節點，計算通過當前選中節點到達它的路徑的長度。如果這個新的路徑長度小於目前已知的最短路徑，則更新目前已知的最短路徑值。
4. 標記節點：標記當前選中節點為已處理。
5. 重複步驟2-4：重複步驟2到4，直到所有節點都被標記為已處理或沒有連接到源節點的節點的最短路徑無限大。
6. 得到最短路徑：一旦所有節點都被處理，你可以獲得從源節點到圖中每個節點的最短路徑。

圖片解說

程式碼

const int INF = numeric_limits<int>::max();
class Graph {
private:
    int vertices, edges; // 點的個數, 邊的個數
    vector<vector<int>> adjMatrix; // 鄰接矩陣
    vector<bool> visited; // 該點是否被訪問過
    vector<int> distance; // 路徑長度
    queue<pair<char,int >> shortPath; // 最短路徑
public:
    Graph(int vertices) : vertices(vertices) {
        edges = 0;
        adjMatrix.resize(vertices);
        for (int i = 0; i < vertices; i++) {
            adjMatrix[i].resize(vertices, 0);
        }
        visited.resize(vertices, false);
        distance.resize(vertices, INF); // 初始化距離為無限大
    }
    
    void addEdge(char from, char to, int weight) {
        adjMatrix[from - 'A'][to - 'A'] = weight;
        edges++;
    }
    
    int minKey() { // 找到最小權重的點
        int min = INF, minIndex=-1;
        for (int v = 0; v < vertices; v++) {
            if (visited[v] == false && distance[v] < min) {
                min = distance[v];
                minIndex = v;
            }
        }
        return minIndex;
    }
    
    void dijkstra(char start) {
        distance[start - 'A'] = 0;
        for (int i = 0; i < vertices ; i++) { // 次數
            int u = minKey();// 找到最小權重的點
            visited[u] = true;
            shortPath.push(make_pair(u+'A',distance[u]));
            for (int v = 0; v < vertices; v++) { // 更新最小權重的點的鄰接點
                if (!visited[v]){ // 如果該點沒有被訪問過
                    // 新的路徑 < 舊的路徑 => 更新路徑
                    if(adjMatrix[u][v] &&  distance[u] + adjMatrix[u][v] < distance[v]){
                        distance[v] = distance[u] + adjMatrix[u][v];
                    }
                }
            }
        }
    }
    void printShortPath(){
        while(!shortPath.empty()){
            cout << shortPath.front().first << ' ' << shortPath.front().second << endl;
            shortPath.pop();
        }
    }

};

Bellman-Ford Algorithm

具體步驟如下：

1. 初始化：創建一個數組或列表，用於存儲每個節點到源節點的目前已知最短路徑估計值。將源節點的最短路徑設置為0，其他節點的最短路徑設置為無窮大。
2. 遍歷邊：對於每條邊，遍歷圖中的所有邊，並對每條邊執行以下操作：
   • 對於每個邊，檢查源節點到該邊的起點的最短路徑估計值加上該邊的權重是否小於目前已知的終點節點的最短路徑估計值。如果是，則更新終點節點的最短路徑估計值為這個更小的值。
3. 重複步驟2：重複執行步驟2 V-1 次，其中 V 是圖中的節點數。這是為了確保在最壞情況下，最短路徑的更新不超過 V-1 次。
4. 檢查負權環路：執行一次額外的遍歷，檢查是否存在負權環路。如果在這個遍歷中仍然發生最短路徑的更新，則表示圖中包含負權環路。
5. 得到最短路徑：如果沒有負權環路存在，則可以獲得從源節點到圖中每個節點的最短路徑。

圖解

程式碼

const int INF = numeric_limits<int>::max();
class Graph { // 圖的結構
private : 
    int vertices, edges; // 點的個數, 邊的個數
    vector<vector<pair<int,int>>> adjMatrix; // 鄰接矩陣 <點,權重>
    vector<int> distance; // 路徑長度
public:
    Graph(int vertices) : vertices(vertices) { // 初始化
        edges = 0;
        adjMatrix.resize(vertices);
        distance.resize(vertices, INF); // 初始化距離為無限大
    }
    void addEdge(char from, char to, int weight) { // 加邊
        adjMatrix[from - 'A'].push_back({to - 'A',weight});
        edges++;
    }
    void printShortPath() { // 印出最短路徑
        cout << "Shortest Path: " << endl;
        for(int i = 0 ; i < vertices ; i++){
            cout << char(i+'A') << ": " << distance[i] << endl;
        }
    }
    void bellmanFord(char start){ //DP 演算法
        distance[start - 'A'] = 0; // 起點的權重為0

        // 遍歷所有點
        for (int i = 0; i < vertices ; i++) { // 需要遍歷的次數為點的個數\
            // 每次遍歷都會更新一次最短路徑
            for(int u = 0 ; u < vertices ; u++){ // 遍歷所有點
                for(auto v : adjMatrix[u]){ // 遍歷所有鄰接點
                    // 新的路徑 < 舊的路徑 => 更新路徑
                    if(distance[u] != INF ){
                        distance[v.first] = min(distance[v.first], distance[u] + v.second);
                    }
                }
            } // O(E)
        } // O(V*E)
        
    }
};

比較表

總結，Dijkstra's Algorithm適用於無負權重邊的單一源最短路徑問題，但不適用於負權重邊。Bellman-Ford Algorithm能處理帶負權重邊的單一源最短路徑，並檢測負權重環路，但效率較低。因此，選擇演算法應基於具體問題的要求和圖的特性。

每個人都有自己的節奏，不需要因為別人會的事情而勉強自己，也不必追求無止境的完美或頂尖。我們不必應付所有事情，也不必將所有知識都吸收。重要的是要了解自己需要的和想要的是什麼。