首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >数据结构与算法-求最短路径之迪杰斯特拉(Dijkstra)算法

数据结构与算法-求最短路径之迪杰斯特拉(Dijkstra)算法

作者头像
越陌度阡
发布2020-11-26 11:18:04
9030
发布2020-11-26 11:18:04
举报

迪杰斯特拉(Dijkstra)算法是典型最短路径算法,用于计算一个节点到其他节点的最短路径,它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想),直到扩展到终点为止。

算法步骤

1. 初始时,引进两个集合S和U,S只包含起点s,U包含除s外的其他顶点,且U中顶点的距离为起点s到该顶点的距离;

2. 从U中选出距离最短的顶点k,并将顶点k加入到S中,同时,将从U中移除顶点k;

3. 更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离,是由于上一步中确定了k是求出最短路径的顶点,从而可以利用k来更新其它顶点的距离。

4. 重复步骤2和3,直到遍历完所有顶点。

算法实例

以图G4为例,以D为起点对该算法进行演示。

以下是实现步骤

算法实现

#include <stdio.h>
#include <string.h>
#include <string>
#include <iostream>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#define mem(a, b) memset(a, b, sizeof(a))
using namespace std;
const int inf = 1 << 29;

int main(){
    int map[10][10], t1, t2, t3, min, u, n, m;
    int dis[10];
    int vis[10];
    scanf("%d%d", &n, &m);
    // 初始化
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            if (i == j){
                map[i][j] = 0;
            }else{
                map[i][j] = inf;
            }
        }
    };
    // 读入边
    for (int i = 1; i <= m; i++){
        scanf("%d%d%d", &t1, &t2, &t3);
        map[t1][t2] = t3;
    };
    // 初始化dis数组,表示1号顶点到其余各个顶点的最短路程
    for (int i = 1; i <= n; i++){
        dis[i] = map[1][i];
    };
    // 初始化vis
    for (int i = 1; i <= n; i++){
        vis[i] = 0;
    };
    // 标记起始点1已经被访问过
    vis[1] = 1; 
    // 迪杰斯特拉算法(Dijkstra)的核心内容
    // 因为松弛的是边数,所以是n-1
    for (int i = 1; i <= n - 1; i++){
        min = inf;
        for (int j = 1; j <= n; j++){
            if (vis[j] == 0 && dis[j] < min){
                min = dis[j];
                u = j;
            }
        };
        vis[u] = 1;
        for (int v = 1; v <= n; v++){
            if (map[u][v] < inf){
                if (dis[u] + map[u][v] < dis[v]){
                    dis[v] = dis[u] + map[u][v];
                }
            }
        }
    };
    for (int i = 1; i <= n; i++){
        printf("%d ", dis[i]);
    }
    return 0;
}

由以上代码中的循环可知,迪杰斯特拉(Dijkstra)算法的时间复杂度是O(n^2)

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2020-06-07 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 算法步骤
  • 算法实例
  • 算法实现
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档