迪杰特斯拉算法（Dijkstra‘s）

迪杰斯特拉算法（Dijkstra's algorithm）是由荷兰计算机科学家艾兹格·迪科斯彻（Edsger W. Dijkstra）在1956年提出的，用于在加权图中找到单个源点到所有其他顶点的最短路径的算法。这个算法广泛应用于网络路由、地图导航等领域。

算法原理

迪杰斯特拉算法的核心思想是贪心算法，它维护一个未访问顶点集合，每次从未访问顶点集合中选择一个距离源点最近的顶点，然后更新该顶点相邻的顶点的距离。

算法步骤

1. 初始化：将源点到自身的距离设为0，到所有其他顶点的距离设为无穷大（∞）。创建一个未访问顶点集合，包含图中所有顶点。

2. 选择顶点：从未访问顶点集合中选择一个距离源点最近的顶点，将其标记为已访问。

3. 更新距离：对于已选择的顶点，检查其所有相邻的未访问顶点，计算通过当前顶点到达这些相邻顶点的距离，并更新它们到源点的距离（如果新计算的距离比之前记录的距离更短）。

4. 重复：重复步骤2和3，直到所有顶点都被访问过。

算法特点

• 效率：迪杰斯特拉算法的时间复杂度为 O(V2)O(V2)，其中 VV 是顶点的数量。使用优先队列可以将其优化到 O((V+E)log⁡V)，其中 E是边的数量。

• 适用性：适用于边权重为非负的图。

• 局限性：如果图中存在负权重边，则迪杰斯特拉算法可能不会给出正确的结果。

代码实现：

#include<bits/stdc++.h>

using namespace std;

int n, m;//n为顶点数，m为边数
int matrix[100][100];//邻接矩阵

//初始化邻接矩阵
void init() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) {
                matrix[i][j] = 0;
            } else {
                matrix[i][j] = INT_MAX;
            }
        }
    }
}

//初始化beginPoint到其他点的距离
vector<int> initBeginDistance(int beginPoint) {
    vector<int> beginDistance;
    for (int i = 0; i < n; i++) {
        beginDistance.push_back(matrix[beginPoint][i]);
    }
    return beginDistance;
}

//更新beginPoint到其他点的距离
void updateMatrix(int beginPoint, vector<int> distances) {
    for (int i = 0; i < n; i++) {
        matrix[beginPoint][i] = distances[i];
    }
}

//打印邻接矩阵
void printMatrix() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << matrix[i][j] << " ";
        }
        cout << endl;
    }
}

int main() {
    cin >> n >> m;
    init();//初始化邻接矩阵
    for (int i = 0; i < m; i++) {
        int x, y, dist;//x为起点，y为终点，distance为距离
        cin >> x >> y >> dist;
        matrix[x][y] = dist;
    }
    vector<int> already, unalready;//already为已经确定最短路径的点，unalready为未确定最短路径的点
    for(int beginPoint = 0; beginPoint < n; beginPoint++) {
        for(int i = 0; i < n; i++) {
            if(i != beginPoint) {
                unalready.push_back(i);
            } else {
                already.push_back(i);
            }
        }
        //初始化beginPoint到其他点的距离
        vector<int> distances = initBeginDistance(beginPoint);
        while(unalready.size() > 0) {
            int minDistance = INT_MAX, minIndex = -1;
            //通过already中的点来更新beginPoint到unalready中的点的距离
            for(int j = 0; j < unalready.size(); j++) {
                if(distances[unalready[j]] <= minDistance) {
                    minDistance = distances[unalready[j]];
                    minIndex = unalready[j];
                }
            }
            //将距离最小的点加入到already中，并从unalready中删除,并且跟新beginPoint到其他点的距离
            already.push_back(minIndex);
            unalready.erase(remove(unalready.begin(), unalready.end(), minIndex), unalready.end());
            // 遍历未访问的节点
            for(int j = 0; j < unalready.size(); j++) {
                // 如果当前节点可以到未访问节点，并且未访问节点的距离大于当前节点到未访问节点的距离加上当前节点的距离
                if(matrix[minIndex][unalready[j]] != INT_MAX && distances[unalready[j]] > distances[minIndex] + matrix[minIndex][unalready[j]]) {
                    // 更新未访问节点的距离
                    distances[unalready[j]] = distances[minIndex] + matrix[minIndex][unalready[j]];
                }
            }
        }
        updateMatrix(beginPoint, distances);
    }
    printMatrix();
    return 0;
}

//输入：
// 5 11
// 0 1 8
// 0 2 32
// 1 0 12
// 1 2 16
// 1 3 15
// 2 1 29
// 2 4 13
// 3 1 21
// 3 4 7
// 4 2 27
// 4 3 19

原文地址：https://blog.csdn.net/release_lonely/article/details/143956383

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！