最短路径(Dijsktra算法)

2024-05-08 16:48
文章标签 算法 路径 最短 dijsktra

本文主要是介绍最短路径(Dijsktra算法),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Dijsktra算法(针对无向图):

初始时,若源点到顶点Vi有边,则D[i]为边上的权值;否则,D[i]为∞。

1)从V0出发,长度最短的最短路径是(V0 ,Vj),即

                    D[j] = min{ D[i] |Vi∈V-S }

      将顶点Vj加入S集合;

2) 求下一条长度最短的路径:

    修改从V0出发到达集合V-S中所有顶点Vk(Vk∈V-S)的路径的长度,即

             如果D[k]> D[j]+arcs[j][k]  (Vk∈V-S)

             则  D[k] = D[j] + arcs[j][k]

      上述路径中长度最小者(Vj)即为下一条长度最短的路径,同时将顶点Vj加入S集合(即将其从集合V-S中去掉);

             D[j]= min { D[i] | Vi∈V-S }

       

3) 重复2)直到求出所有顶点的最短路径。

下面上实现的代码:
#include <stdio.h>
#include <stdlib.h>const int IFINITY = 99999999;
const int N = 50;/*
测试数据 
6 10
1 2 6
1 3 1
1 4 5
2 3 5
3 4 5
2 5 3 
3 5 6
3 6 4
4 6 2
5 6 6
*/int map[N][N], n;
int D[N], p[N][N];void Dijsktra()
{int final[N], min, v0 = 1;int v, w, i, j, k, z;for(v = 1; v <= n; v++){final[v] = 0;D[v] = map[v0][v];for(w = 1; w <= n; ++w)p[v][w] = 0;if(D[v] < IFINITY){p[v][v0] = 1;p[v][v] = 1;}}D[v0] = 0;//集合S置初值final[v0] = 1;for(i = 1; i < n; i++)  //求其余顶点的最短路径{//求其余终点的最短路径min = IFINITY;for(k = 1; k <= n; ++k)if(final[k] == 0)//顶点Vk不在集合S中if(D[k] < min){j = k;min = D[k];}             // V0至Vk的路径长度更短时,更新min并用j记下顶点kfinal[j] = 1;   //求出了V0到Vj的最短路径,将Vj加入集合Sfor(k = 1; k <= n; ++k)//更新其余顶点的路径及长度if(final[k] == 0 && (D[j] + map[j][k] < D[k])){D[k] = D[j] + map[j][k]; //更新Vk的路径长度for(z = 1; z <= n; ++z)p[k][z] = p[j][z];//更新Vk的路径p[k][k] = 1;      //将Vk加入V0到Vk的路径中}}} int main()
{int m, s, e, w;scanf("%d %d", &n, &m);for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)map[i][j] =  IFINITY;for(int j = 1; j <= m; j++){scanf("%d %d %d", &s, &e, &w);map[s][e] = map[e][s] = w;}Dijsktra();for(int k = 1; k <= n; k++){printf("第一个顶点到顶点%d的最短路径为:\n",k);for(int j = 1; j <= n; j++){if(p[k][j] == 1)printf("%d ", j);//打印路径 }     printf("代价为: %d\n\n", D[k]);    //打印总距离 }system("pause");return 0;
}



这篇关于最短路径(Dijsktra算法)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/970878

相关文章

Spring Boot中的路径变量示例详解

《SpringBoot中的路径变量示例详解》SpringBoot中PathVariable通过@PathVariable注解实现URL参数与方法参数绑定,支持多参数接收、类型转换、可选参数、默认值及... 目录一. 基本用法与参数映射1.路径定义2.参数绑定&nhttp://www.chinasem.cnbs

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

SpringBoot项目配置logback-spring.xml屏蔽特定路径的日志

《SpringBoot项目配置logback-spring.xml屏蔽特定路径的日志》在SpringBoot项目中,使用logback-spring.xml配置屏蔽特定路径的日志有两种常用方式,文中的... 目录方案一:基础配置(直接关闭目标路径日志)方案二:结合 Spring Profile 按环境屏蔽关

VSCode设置python SDK路径的实现步骤

《VSCode设置pythonSDK路径的实现步骤》本文主要介绍了VSCode设置pythonSDK路径的实现步骤,包括命令面板切换、settings.json配置、环境变量及虚拟环境处理,具有一定... 目录一、通过命令面板快速切换(推荐方法)二、通过 settings.json 配置(项目级/全局)三、

使用Python和Matplotlib实现可视化字体轮廓(从路径数据到矢量图形)

《使用Python和Matplotlib实现可视化字体轮廓(从路径数据到矢量图形)》字体设计和矢量图形处理是编程中一个有趣且实用的领域,通过Python的matplotlib库,我们可以轻松将字体轮廓... 目录背景知识字体轮廓的表示实现步骤1. 安装依赖库2. 准备数据3. 解析路径指令4. 绘制图形关键

如何更改pycharm缓存路径和虚拟内存分页文件位置(c盘爆红)

《如何更改pycharm缓存路径和虚拟内存分页文件位置(c盘爆红)》:本文主要介绍如何更改pycharm缓存路径和虚拟内存分页文件位置(c盘爆红)问题,具有很好的参考价值,希望对大家有所帮助,如有... 目录先在你打算存放的地方建四个文件夹更改这四个路径就可以修改默认虚拟内存分页js文件的位置接下来从高级-

一文详解如何查看本地MySQL的安装路径

《一文详解如何查看本地MySQL的安装路径》本地安装MySQL对于初学者或者开发人员来说是一项基础技能,但在安装过程中可能会遇到各种问题,:本文主要介绍如何查看本地MySQL安装路径的相关资料,需... 目录1. 如何查看本地mysql的安装路径1.1. 方法1:通过查询本地服务1.2. 方法2:通过MyS

使用雪花算法产生id导致前端精度缺失问题解决方案

《使用雪花算法产生id导致前端精度缺失问题解决方案》雪花算法由Twitter提出,设计目的是生成唯一的、递增的ID,下面:本文主要介绍使用雪花算法产生id导致前端精度缺失问题的解决方案,文中通过代... 目录一、问题根源二、解决方案1. 全局配置Jackson序列化规则2. 实体类必须使用Long封装类3.

Springboot实现推荐系统的协同过滤算法

《Springboot实现推荐系统的协同过滤算法》协同过滤算法是一种在推荐系统中广泛使用的算法,用于预测用户对物品(如商品、电影、音乐等)的偏好,从而实现个性化推荐,下面给大家介绍Springboot... 目录前言基本原理 算法分类 计算方法应用场景 代码实现 前言协同过滤算法(Collaborativ

Python如何调用指定路径的模块

《Python如何调用指定路径的模块》要在Python中调用指定路径的模块,可以使用sys.path.append,importlib.util.spec_from_file_location和exe... 目录一、sys.path.append() 方法1. 方法简介2. 使用示例3. 注意事项二、imp