迪杰斯特拉(Dijkstra)算法求图中最短路径

迪杰斯特拉(Dijkstra )算法

对于图G=(V,E),将图的顶点分为两组: 顶点集S:已求出的最短路径的顶点集合(初始为{v0}); 顶点集V-S:尚未求出最短路径的顶点集合(初始为V-{v0} )。 算法按最短路径长度的递增顺序逐个将V-S的顶点加入S中,直到所有顶点均被加入S为止。 算法需借助辅助数组dist[N], dist[i]表示目前已经找到的、从开始点v0到终点vi的当前最短路径的长度。 dist各元素的初值:若从v0到vi存在弧,则dist[i]为弧上的权值;否则dist[i]为∞。

算法执行过程

(1)当前下一条长度最短的路径必为 ( v0, … , vk ),vk满足如下条件: dist[k]=Min{dist[i] | vi∈V-S} 求得顶点vk的最短路径后,将vk加入顶点集S中。 修正:每加入一个新的顶点vk到顶点集S,则对V-S中剩余的各顶点,多了一个“中转”结点vk,从而可能多一条“中转”路径,新的中转路径可能小于原来的路径,所以需对V-S剩余的各顶点的最短路径长度dist[i]进行修正。

(2)如何修正? 原来v0到vi的最短路径长度为dist[i],加入vk后,以vk为中间顶点的“中转”路径长度为:dist[k] + wki,(wki为弧”<”vk, vi>上的权值),若“中转”路径长度小于原dist[i](即 dist[k] + wki < dist[i]),则将顶点vi的最短路径长度修正为“中转”路径的长度。 (3)重复上述步骤(1)(2),直到所有顶点均加入S为止。

另外,为了记录从v0出发到各顶点的最短“路径”(顶点序列),使用辅助数组path[ ], path[i]表示当前找到的从开始顶点v0到顶点vi的当前最短路径顶点序列。 path[N]各元素的初值:如果从v0到vi有弧存在,则path[i]为(v0, vi);否则path[i]为空。

//Dijkstra算法
#define INFINITY 32768
typedef unsigned int WeightType
typedef WeightType Adjtex
typedef Seqlist VertexSet;

ShortestPath_DJS(AdjMartrix g, int v0, WeightType dist[MAX_VERTEX_NUM],
VertexSet path[MAX_VERTEX_NUM]) {
/*path[i]中存放当前顶点i的最短路径,是一个线性表。dist[i]中存放顶点i的当前最短路径长度*/
    VertexSet s;     /*s为已找到最短路径的终点集合*/
    for(i = 0; i < g.vexnum; i++) {
        InitList(&path[i]);               /*初始化dist[i]和path[i]*/
        dist[i] = g.arcs.[v0][i].adj;     /*dist[i]初始放当前顶点i到v0的路径长度*/
        if(dist[i] < INFINITY) {          /*如果经过上一步权值存在(路径存在)*/
            AddTail(&path[i], g.vertex[v0]);     /*AddTail是表尾添加操作*/
            AddTail(&path[i], g.vertex[i]);      /*构造从v0到i的路径序列,存储在顺序表数组的第i行*/
        }
    }
    InitList(&s);
    AddTail(&s, g.vertex[v0]);                /*将v0看成第一个已找到最短路径的终点*/
    for(t = 1; t <= g.vexnum - 1; t++) {      /*求v0到其余n-1个顶点额最短路径(n=g.vexnum)*/
        min = INFINITY;
        for(i = 0; t <= g.vexnum; i++) {
            if(!Member(g.vertex[i], s) && dist[i] < min) {//该点不存在s集合中且该点到v0的路径存在
                k = i; min = dist[i];
            }
        }
        if(min == INFINITY) return;   //如果经过上步没有修改min的值,说明当前顶点到v0没有路径 回退
        AddTail(&s, g.vertex[k]);     //把当前顶点加到s集合中
        for(i = 0; i < g.vertex; i++) {
        //如果该顶点不在s集合中且路径存在且该点通过已经加进s集合的点建立的新路径长度小于原路径
            if(!Member(g.vertex[i], s) && g.arcs[k][i].adj != INFINITY 
                       && (dist[k] + g.arc[k][i].adj < dist[i]) {
                dist[i] = dist[k] + g.arcs[k][i].adj;    //修改dist[i]为即最新的最短路径长度
                path[i] = path[k];                       //更新路径
                AddTail(&path[i], g.vertex[i]);     /*path[i] = path[k]∪{vi}*/                          
            }
        }
    }
}

知乎:Solo | 微博@从流域到海域

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏软件开发 -- 分享 互助 成长

图的遍历算法

前言:学习图的遍历算法之前,需要先了解一下图的存储方式(这里只以无向图作为讨论了)。 (1)邻接矩阵 ? (2)邻接表 ? 一、DFS(深度优先遍历)  设置一...

2087
来自专栏青玉伏案

iOS开发之Masonry框架源码解析

Masonry是iOS在控件布局中经常使用的一个轻量级框架,Masonry让NSLayoutConstraint使用起来更为简洁。Masonry简化了NSLay...

2168
来自专栏聊聊技术

原 初学图论-Kahn拓扑排序算法(Kah

3478
来自专栏聊聊技术

原 初学图论-DAG单源最短路径算法

38612
来自专栏机器学习与自然语言处理

图的遍历之深度优先搜索(DFS)

深度优先搜索(depth-first search)是对先序遍历(preorder traversal)的推广。”深度优先搜索“,顾名思义就是尽可能深的搜索一个...

35810
来自专栏潇涧技术专栏

Python Algorithms - C2 The basics

本节主要介绍了三个内容:算法渐近运行时间的表示方法、六条算法性能评估的经验以及Python中树和图的实现方式。

1122
来自专栏机器学习与自然语言处理

深度优先生成树及其应用

在上一篇博客判断有向图是否有圈中从递归的角度简单感性的介绍了如何修改深度优先搜索来判断一个有向图是否有圈。事实上, 它的实质是利用了深度优先生成树(depth-...

3907
来自专栏聊聊技术

原 初学图论-Bellman-Ford单源

46013
来自专栏落影的专栏

Metal入门教程总结

本文介绍Metal和Metal Shader Language,以及Metal和OpenGL ES的差异性,也是实现入门教程的心得总结。

1.1K6
来自专栏技术碎碎念

LeetCode-70-Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top. Each time y...

36212

扫码关注云+社区

领取腾讯云代金券