Dijkstras 最短路徑演算法

在繼續之前，建議你簡要介紹一下 Adjacency Matrix 和 BFS

Dijkstra 演算法被稱為單源最短路徑演算法。它用於查詢圖中節點之間的最短路徑，其可以表示例如道路網路。它由 Edsger W. Dijkstra於 1956 年構思，三年後出版。

我們可以使用廣度優先搜尋（BFS）搜尋演算法找到最短路徑。該演算法工作正常，但問題是，它假設遍歷每條路徑的成本相同，這意味著每條邊的成本是相同的。Dijkstra 演算法幫助我們找到每條路徑成本不同的最短路徑。

首先我們將看到，如何修改 BFS 以編寫 Dijkstra 演算法，然後我們將新增優先順序佇列以使其成為完整的 Dijkstra 演算法。

假設每個節點與源的距離保持在 d [] 陣列中。如同， d [3] 表示 d [3] 時間從源到達節點 3 。如果我們不知道距離，我們將在 d [3]中儲存無窮大。另外，讓 [u] [v] 代表 uv 的成本。這意味著從 u 節點到 v 節點需要花費[u] [v] 。 ** **** **** **** **** **** ****

我們需要了解 Edge Relaxation。比方說，從你的房子，即源頭，到 A 的位置需要 10 分鐘。而且要花 B 分鐘需要 25 分鐘。我們有， **** ** ****

d[A] = 10
d[B] = 25

現在讓我們說從 A 地到 B 處需要 7 分鐘，這意味著： **** ****

cost[A][B] = 7

然後，我們可以去放置B從源通過進入放置A從源，然後從一個地方A，要去的地方B，這將需要 10 + 7 = 17 分鐘，而不是 25 分鐘。所以，

d[A] + cost[A][B] < d[B]

然後我們更新，

d[B] = d[A] + cost[A][B]

這叫做放鬆。我們將從節點 u 到節點 v ，如果 **d [u] + cost [u] [v] <d [v]，**那麼我們將更新 d [v] = d [u] + cost [u] [v] 。

在 BFS 中，我們不需要兩次訪問任何節點。我們只檢查了是否訪問過某個節點。如果沒有訪問它，我們將節點推入佇列，將其標記為已訪問並將距離增加 1.在 Dijkstra 中，我們可以推送佇列中的節點，而不是使用訪問更新它，我們放鬆或更新新邊緣。我們來看一個例子：

我們假設，節點 1 是源。然後，

d[1] = 0
d[2] = d[3] = d[4] = infinity (or a large value)

我們將 d [2]，d [3] 和 d [4]設定為*無窮大，*因為我們還不知道距離。而源的距離當然是 0 。現在，我們從原始碼轉到其他節點，如果我們可以更新它們，那麼我們將它們推入佇列中。比方說，我們將遍歷邊緣 1-2 。當 d [1] + 2 <d [2]時， d [2] = 2 。類似地，我們將遍歷邊緣 1-3 ，這使得 d [3] = 5 。

我們可以清楚地看到 5 不是我們可以跨越到節點 3 的最短距離。因此，像 BFS 一樣只遍歷一個節點在這裡不起作用。如果我們使用邊緣 2-3 從節點 2 到節點 3 ，我們可以更新 d [3] = d [2] + 1 = 3 。所以我們可以看到一個節點可以多次更新。你問多少次？節點可以更新的最大次數是節點的度數。 **** ****

讓我們看一下多次訪問任何節點的虛擬碼。我們將簡單地修改 BFS：

procedure BFSmodified(G, source):
Q = queue()
distance[] = infinity
Q.enqueue(source)
distance[source]=0
while Q is not empty
    u <- Q.pop()
    for all edges from u to v in G.adjacentEdges(v) do
        if distance[u] + cost[u][v] < distance[v]
            distance[v] = distance[u] + cost[u][v]
        end if
    end for
end while
Return distance

這可用於從源中查詢所有節點的最短路徑。這段程式碼的複雜性不太好。這就是原因，

在 BFS 中，當我們從節點 1 到所有其他節點時，我們遵循先到先服務方法。例如，我們在處理節點 2 之前從源到節點 3 。如果我們從源轉到節點 3 ，我們將節點 4 更新為 5 + 3 = 8 。當我們再次從節點 2 更新節點 3 時，我們需要再次將節點 4 更新為 3 + 3 = 6 ！ 因此節點 4 更新兩次。 **** **** **** **** **** **** **** **** **** **** ****

Dijkstra 建議，如果我們先更新最近的節點，而不是先到先服務方法，那麼它將需要更少的更新。如果我們之前處理過節點 2 ，那麼節點 3 之前就已經更新，並且在相應地更新節點 4 之後，我們很容易得到最短的距離！ 我們的想法是從最靠近源的佇列中選擇節點。所以我們將在這裡使用 Priority Queue ，這樣當我們彈出佇列時，它將為我們帶來離源最近的節點 u 。它會怎麼做？它會用它來檢查 d [u] 的值。 **** ****

我們來看看虛擬碼：

procedure dijkstra(G, source):
Q = priority_queue()
distance[] = infinity
Q.enqueue(source)
distance[source] = 0
while Q is not empty
    u <- nodes in Q with minimum distance[]
    remove u from the Q
    for all edges from u to v in G.adjacentEdges(v) do
        if distance[u] + cost[u][v] < distance[v]
            distance[v] = distance[u] + cost[u][v]
            Q.enqueue(v)
        end if
    end for
end while
Return distance

虛擬碼返回所有其他節點與源的距離。如果我們想知道單個節點 v 的距離，我們可以簡單地在從佇列中彈出 v 時返回該值。

現在，Dijkstra 演算法在出現負邊緣時是否有效？如果存在負迴圈，則會出現無限迴圈，因為它會每次都降低成本。即使存在負邊緣，Dijkstra 也無法工作，除非我們在彈出目標後立即返回。但是，它不會是 Dijkstra 演算法。我們需要 Bellman-Ford 演算法來處理負邊緣/週期。

複雜：

BFS 的複雜度為 O（log（V + E）） ，其中 V 是節點數， E 是邊數。對於 Dijkstra，複雜性類似，但優先順序佇列的排序需要 O(logV) 。總複雜度為： O（Vlog(V)+ E）

下面是使用鄰接矩陣求解 Dijkstra 最短路徑演算法的 Java 示例

import java.util.*;
import java.lang.*;
import java.io.*;

class ShortestPath
{
    static final int V=9;
    int minDistance(int dist[], Boolean sptSet[])
    {
        int min = Integer.MAX_VALUE, min_index=-1;

        for (int v = 0; v < V; v++)
            if (sptSet[v] == false && dist[v] <= min)
            {
                min = dist[v];
                min_index = v;
            }

        return min_index;
    }

    void printSolution(int dist[], int n)
    {
        System.out.println("Vertex Distance from Source");
        for (int i = 0; i < V; i++)
            System.out.println(i+" \t\t "+dist[i]);
    }

    void dijkstra(int graph[][], int src)
    {

        Boolean sptSet[] = new Boolean[V];

        for (int i = 0; i < V; i++)
        {
            dist[i] = Integer.MAX_VALUE;
            sptSet[i] = false;
        }

        dist[src] = 0;

        for (int count = 0; count < V-1; count++)
        {
            int u = minDistance(dist, sptSet);

            sptSet[u] = true;

            for (int v = 0; v < V; v++)

                if (!sptSet[v] && graph[u][v]!=0 &&
                        dist[u] != Integer.MAX_VALUE &&
                        dist[u]+graph[u][v] < dist[v])
                    dist[v] = dist[u] + graph[u][v];
        }

        printSolution(dist, V);
    }

    public static void main (String[] args)
    {
    int graph[][] = new int[][]{{0, 4, 0, 0, 0, 0, 0, 8, 0},
                                {4, 0, 8, 0, 0, 0, 0, 11, 0},
                                {0, 8, 0, 7, 0, 4, 0, 0, 2},
                                {0, 0, 7, 0, 9, 14, 0, 0, 0},
                                {0, 0, 0, 9, 0, 10, 0, 0, 0},
                                {0, 0, 4, 14, 10, 0, 2, 0, 0},
                                {0, 0, 0, 0, 0, 2, 0, 1, 6},
                                {8, 11, 0, 0, 0, 0, 1, 0, 7},
                                {0, 0, 2, 0, 0, 0, 6, 7, 0}
                                };
        ShortestPath t = new ShortestPath();
        t.dijkstra(graph, 0);
    }
}

該計劃的預期產出是

Vertex   Distance from Source
0                0
1                4
2                12
3                19
4                21
5                11
6                9
7                8
8                14