526互联

Dijkstra 算法——求解最短路径问题

发布时间 2023-07-25 16:42:58作者: 卑以自牧lq

Dijkstra 算法——求解最短路径问题

  迪杰斯特拉算法（Dijkstra's algorithm）是一种用于解决单源最短路径问题的贪心算法。它可以找到从一个起始顶点到其他所有顶点的最短路径，并且适用于边的权重非负的图。

算法步骤如下：

  1. 创建一个数组 dist，用于保存起始顶点到其他顶点的最短距离。初始化 dist 数组，将起始顶点的距离设置为0，其他顶点的距离设置为无穷大（或者一个很大的值）。
  2. 创建一个集合 visited，用于记录已经确定最短路径的顶点。
  3. 重复以下步骤，直到所有顶点都在 visited 集合中：
    a. 从 dist 数组中选择当前距离最小的顶点 u，将其加入 visited 集合。
    b. 对于 u 的所有未访问的邻居顶点 v，更新其距离：dist[v] = min(dist[v], dist[u] + weight(u, v))，其中 weight(u, v) 表示边 (u, v) 的权重。
  4. 最终，dist 数组中存储的就是起始顶点到其他所有顶点的最短距离。

  本质上是维护两个集合，S 集合表示已处理的点，U 集合表示未处理的点。每次把一个点从 U 放到 S 里，同时要更新 S 中的点到 U 中的点的距离。直到 U 中没有点。

  Dijkstra 算法的关键点在于每次选择距离最小的顶点并更新与该顶点相邻的顶点的距离，这样逐步扩展最短路径。算法的正确性基于贪心策略：每次找到距离最小的顶点，该顶点的最短路径已经确定，不再需要重新访问。

  需要注意的是，Dijkstra 算法要求边的权重非负。如果存在负权边，应该使用 Bellman-Ford 算法来解决单源最短路径问题。

c++代码示例

vector<int> dijkstra(const vector<vector<int>>& graph, int start, unordered_map<int, int>& pre) {
    int n = graph.size();
    vector<int> dist(n, INT_MAX);
    vector<bool> visited(n, false);

    dist[start] = 0;

    for (int i = 0; i < n - 1; ++i) {
        int u = -1;
        // 找到起点到未访问的节点中距离最短的点
        for (int j = 0; j < n; ++j) {
            if (!visited[j] && (u == -1 || dist[j] < dist[u])) {
                u = j;
            }
        }

        visited[u] = true;

        // 更新起点到所有的点的距离，判断从点 u 到其它的点是否会更近
        for (int v = 0; v < n; ++v) {
            if (graph[u][v] != 0 && !visited[v]) {
                if (dist[v] > dist[u] + graph[u][v]) {
                    dist[v] = dist[u] + graph[u][v];
                    pre[v] = u; // 记录路径
                }

            }
        }
    }

    return dist;
}

// 获取起始节点到某个节点的路径
vector<int> getPath(int start, int end, const unordered_map<int, int>& predecessors) {
    vector<int> path;
    int current = end;
    while (current != start) {
        path.push_back(current);
        current = predecessors.at(current);
    }
    path.push_back(start);
    reverse(path.begin(), path.end());
    return path;
}

测试

int main() {
    vector<vector<int>> graph = {
        {0, 10, 3, 0},
        {10, 0, 0, 2},
        {3, 0, 0, 7},
        {0, 2, 7, 0}
    };

    int start = 0;
    unordered_map<int, int> pre;
    vector<int> shortestDist = dijkstra(graph, start, pre);

    // 起始节点到其它节点的最短路径大小
    for (unsigned i = 0; i < shortestDist.size(); ++i) {
        cout << "Vertex " << i << ": " << shortestDist[i] << endl;
    }

    // 打印起始节点到节点 3 的具体路径
    vector<int> path = getPath(start, 3, pre);
    for (auto it : path) {
        cout << it << " ";
    }
    cout << endl;

    return 0;
}

测试例子中表示的图为：
img