Dijkstra 的最短路径算法

Dijkstra 的最短路径算法
在继续之前，建议简要了解邻接矩阵和BFS

迪克斯特拉算法 （打开新窗口）称为单源最短路径算法。它用于查找图形中节点之间的最短路径，例如，可能表示道路网络。它是由埃德斯格·迪克斯特拉 （打开新窗口）1956年出版，三年后出版。

我们可以使用广度优先搜索（BFS）搜索算法找到最短路径。此算法工作正常，但问题是，它假设遍历每条路径的成本相同，这意味着每个边的成本相同。Dijkstra的算法帮助我们找到每条路径的成本不相同的最短路径。

首先，我们将看到，如何修改BFS来编写Dijkstra的算法，然后我们将添加优先级队列以使其成为完整的Dijkstra算法。

假设每个节点与源的距离保持在 d[] 数组中。如 in 所示，d[3] 表示 d[3] 时间是从源到达节点 3 的。如果我们不知道距离，我们将在d[3]中存储无穷大。此外，让 cost[u][v] 表示 u-v 的成本。这意味着从 u 节点转到 v 节点需要 cost[u][v]。

成本[u][v]说明（打开新窗口）

我们需要了解边缘放松。比方说，从你的房子，也就是源头，需要10分钟才能到达A地。去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 之后，我们很容易得到最短的距离！我们的想法是从最接近源的队列，节点中进行选择。因此，我们将在此处使用优先级队列，以便当我们弹出队列时，它将为我们带来来自源的最接近的节点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算法。我们需要贝尔曼-福特 （打开新窗口）用于处理负边/周期的算法。

复杂性：

BFS 的复杂性是 O（log（V+E）），其中 V 是节点数，E 是边数。对于 Dijkstra，复杂性是相似的，但优先级队列的排序需要 O（logV）。所以总复杂度是：O（Vlog（V）+E）

下面是一个 Java 示例，用于使用邻接矩阵求解 Dijkstra 的最短路径算法

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