圆咕噜咕噜 发表于 5 天前

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

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

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


[*] 初始化：将源点到自身的间隔设为0，到所有其他极点的间隔设为无穷大（∞）。创建一个未访问极点集合，包罗图中所有极点。
[*] 选择极点：从未访问极点集合中选择一个间隔源点最近的极点，将其标记为已访问。
[*] 更新间隔：对于已选择的极点，查抄其所有相邻的未访问极点，盘算通过当前极点到达这些相邻极点的间隔，并更新它们到源点的间隔（如果新盘算的间隔比之前记载的间隔更短）。
[*] 重复：重复步骤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;//邻接矩阵

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

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

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

//打印邻接矩阵
void printMatrix() {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
            cout << matrix << " ";
      }
      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 = 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] <= minDistance) {
                  minDistance = distances];
                  minIndex = unalready;
                }
            }
            //将距离最小的点加入到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] != INT_MAX && distances] > distances + matrix]) {
                  // 更新未访问节点的距离
                  distances] = distances + matrix];
                }
            }
      }
      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

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页: [1]
查看完整版本: 迪杰特斯拉算法（Dijkstra‘s）