动态规划求多段图的最短路径

一、基本思想

动态规划法将待求解问题分解成若干个相互重叠的子问题,每个子问题相互关联;动态规划法与分治法的区别就在于分治法的子问题相互不关联,而动态规划法的子问题是相互关联的,且有重叠的部分。

二、算法分析

动态规划法求多段图的最短路径,根据起始节点,寻找与该节点相连且路径最短的那个节点,以寻找到的结点以起始节点,找下一个与其路径最短的那个节点,判断这三个节点之间是否还有一组解,比我们第一次找到的路径还要短,若存在,且是最短的,则将上一组解替换为我们找到的最优解,依次找出其他节点的最短路径,直至最后一个点,那么得出的解就是本问题的最优解。

for (j = 1;j < n;j++) {  
		for (i = j - 1;i >= 0;i--) {//前驱节点
			if (cost[i] + node[i][j] < cost[j]) {
				cost[j] = cost[i] + node[i][j]; // 更新值 
				path[j] = i; // 将i的值告诉j 
			}
		}
	}

 三、问题描述

四、代码实现

#include<iostream>
using namespace std;
#define INF 999//宏定义常量
int node[100][100]; // 最多100个点 
int CreateGraph()
{
	int point, edge;
	cout << "请输入顶点和边的个数:" << endl;
	cin >> point >> edge;
	for (int i = 0;i < point;i++) { // 初始化边的权值 
		for (int j = 0;j < point;j++) {
			node[i][j] = INF;
		}
	}
	int weight;
	for (int k = 0;k < edge;k++) {
		int i, j;
		cout << "请输入第" << k + 1 << "条边的两个顶点和权值:" << endl;
		cin >> i >> j >> weight;
		node[i][j] = weight;
	}
	return point;  
}

// 求 n个顶点的多段图的最短路径 
int Path(int n)
{
	int i, j;
	int cost[100], path[100]; // 存储路径长度和路径 
	for (i = 1;i < n;i++) {
		cost[i] = INF;//初始化
		path[i] = -1;
	}
	cost[0] = 0;
	path[0] = -1;
	for (j = 1;j < n;j++) {  
		for (i = j - 1;i >= 0;i--) {//前驱节点
			if (cost[i] + node[i][j] < cost[j]) {
				cost[j] = cost[i] + node[i][j]; // 更新值 
				path[j] = i; // 将i的值告诉j 
			}
		}
	}
	i = n - 1;
	cout << i;
	while (path[i] >= 0) { 
		cout << "<-" << path[i];
		i = path[i]; // 更新为前一个点 
	}
	cout << endl;
	return cost[n - 1]; // 返回最短路径长度 
}

int main()
{
	cout << "最短路径长度为:" << Path(CreateGraph()) << endl;

	return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/689665.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

细说NLP中的Embedding层

文章目录 前言一、为什么要引入Embedding层二、Embedding层是怎么发挥作用的&#xff1f;三、感受Embedding的强大四、为什么理解Embedding的底层原理&#xff1f;总结 前言 在构建高效的自然语言处理模型时&#xff0c;Embedding层是不可或缺的组成部分。它不仅可以帮助我们捕…

【免费Web系列】大家好 ,今天是Web课程的第十七天点赞收藏关注,持续更新作品 !

这是Web第一天的课程大家可以传送过去学习 http://t.csdnimg.cn/K547r SpingBoot原理 在前面十多天的课程当中&#xff0c;我们学习的都是web开发的技术使用&#xff0c;都是面向应用层面的&#xff0c;我们学会了怎么样去用。而我们今天所要学习的是web后端开发的最后一个篇…

通过影刀RPA,创建定时任务,自动获取图片验证码登录平台;

1.下载下载影刀客户端-影刀RPA - 影刀官网 2.安装&#xff0c;登录 3.应用创建->PC自动化应用 4.按照流程-创建【可双击或拖动】 5.保存 6.右击【创建的应用】->发版 7.选择触发器->【定时触发器】 根据提示配置 8.完成&#xff0c;每天平台会自动打开&#xff1b;…

文章解读与仿真程序复现思路——电网技术EI\CSCD\北大核心《基于日间-日内不确定集的中长期电源扩展规划》

本专栏栏目提供文章与程序复现思路&#xff0c;具体已有的论文与论文源程序可翻阅本博主免费的专栏栏目《论文与完整程序》 论文与完整源程序_电网论文源程序的博客-CSDN博客https://blog.csdn.net/liang674027206/category_12531414.html 电网论文源程序-CSDN博客电网论文源…

TCP攻击是怎么实现的,如何防御?

TCP&#xff08;Transmission Control Protocol&#xff09;是互联网协议族中的重要组成部分&#xff0c;用于在不可靠的网络上提供可靠的数据传输服务。然而&#xff0c;TCP协议的一些特性也使其成为攻击者的目标&#xff0c;尤其是DDoS&#xff08;Distributed Denial of Ser…

正确挑选百兆超薄款工业级网络/脉冲变压器(网络隔离滤波器)

Hqst华强盛&#xff08;石门盈盛电子&#xff09;导读&#xff1a;工业级百兆超薄款网络变压器的生产要特殊的超薄磁芯配正确线径的铜线&#xff0c;使用符合相应防潮标准的凝固胶水。 一 ̖ 首先来看下商业级的超薄款的百兆网络变压器&#xff1a; 商业级&#xff08;消费级&…

基于Zero-shot实现LLM信息抽取

基于Zero-shot方式实现LLM信息抽取 在当今这个信息爆炸的时代&#xff0c;从海量的文本数据中高效地抽取关键信息显得尤为重要。随着自然语言处理&#xff08;NLP&#xff09;技术的不断进步&#xff0c;信息抽取任务也迎来了新的突破。近年来&#xff0c;基于Zero-shot&#x…

Linux CGroup资源限制(概念限制进程CPU使用)

Linux CGroup资源限制&#xff08;详解&#xff09; 最近客户认为我们程序占用cpu过高&#xff0c;希望我们限制&#xff0c;排查之后发现是因为程序频繁gc导致&#xff0c;为了精细化、灵活的的限制&#xff0c;想到了使用Linux CGroup。 0 前置知识 ①概念及作用 官网&#…

给Mac添加右键菜单「使用 VSCode 打开」的方法

用 macOS 系统的苹果电脑用户都知道&#xff0c;macOS 某些地方确实没 Windows 方便&#xff0c;比如右键菜单&#xff0c;没有复制粘贴之类的菜单&#xff0c;刚开始还有点使用不方便&#xff0c;今天我介绍两种方法来实现一个用右键通过 VSCode 打开文件和文件夹的方法&#…

Redis实战——创建账户及连接数据库

一、创建一个新账户 要创建一个带有免费数据库的新账户&#xff0c;请按照以下步骤操作&#xff1a; 前往 Redis Cloud 的注册页面。有两种开始使用 Redis Cloud 的选项&#xff1a; 在表单中输入您的信息&#xff0c;然后选择“Get Started”&#xff08;开始使用&#xff…

Golang使用讯飞星火AI接口

一、API申请 https://www.bilibili.com/video/BV1Yw411m7Rs/?spm_id_from333.337.search-card.all.click&vd_source707ec8983cc32e6e065d5496a7f79ee6 注册申请&#xff0c;需要在此页面获取appid、apisecret、apikey https://www.xfyun.cn/ https://console.xfyun.cn/ser…

隐式链接DLL

本文仅供学习交流&#xff0c;严禁用于商业用途&#xff0c;如本文涉及侵权请及时联系本人将于及时删除 【例9.5】创建的基于MFC对话框的应用程序MFCImLink2&#xff0c;隐式链接例9.2创建的MFCLibrary2.dll&#xff0c;使用其中的导出函数求正方形的面积。 (1) 使用MFC应用程…

PS的stable diffusion插件安装指南

PS的stable diffusion插件安装指南 1.首先要安装stable diffusion&#xff0c;具体安装方法&#xff0c;参考https://blog.csdn.net/sheji888/article/details/139196688 stable diffusion要求要启用API功能 2.安装ps2023以上版本&#xff0c;低于这个版本不能使用stable diff…

尝试使用blazor(一)吐槽blazor,未开始之前,先吐为敬

为什么要写一点关于blazor的文章呢?其实是没什么人看的&#xff0c;我知道blazor目前在国内使用的人数&#xff0c;恐怕一辆大巴车都坐不满。非常冷门&#xff0c;我刚用blazor遇到问题&#xff0c;花钱找人解决&#xff0c;找了国内几个著名的平台&#xff0c;几乎没人会blaz…

关于怎么用Cubemx生成的USBHID设备实现读取一体的鼠标键盘设备(改进版)

主要最近做了一个要用STM32实现读取鼠标键盘一体的那种USB设备&#xff0c;STM32的界面上要和电脑一样的能通过这个USB接口实现鼠标移动&#xff0c;键盘的按键。然后我就很自然的去参考了正点原子的例程&#xff0c;可是找了一圈&#xff0c;发现正点原子好像用的库函数&#…

短剧看剧系统投流版系统搭建,前端uni-app

目录 前言&#xff1a; 一、短剧看剧系统常规款短剧系统和投流版的区别&#xff1f; 二、后端体系 1.管理端&#xff1a; 2.代理投流端 三、功能区别 总结&#xff1a; 前言&#xff1a; 23年上半年共上新微短剧481部&#xff0c;相较于2022年全年上新的454部&#xff0…

使用el-tree封装一个权限管理的小功能

使用el-tree封装一个权限管理的小功能 使用el-tree封装权限管理, 选中人员并且在右侧回显, 此组件用到了递归, 我只是将需要显示的数据进行了动态传递, 其他数据小伙伴可以自己封装 父组件 <template><div><authorityManage ref"authorityManage" :…

Vuepress 2从0-1保姆级进阶教程——标准化流程

Vuepress 2 专栏目录 1. 入门阶段 Vuepress 2从0-1保姆级入门教程——环境配置篇Vuepress 2从0-1保姆级入门教程——安装流程篇Vuepress 2从0-1保姆级入门教程——文档配置篇Vuepress 2从0-1保姆级入门教程——范例与部署 2.进阶阶段 Vuepress 2从0-1保姆级进阶教程——全文搜索…

学习笔记——路由网络基础——路由概述

一、路由概述 1、路由定义与作用 路由(routing)是指导报文转发路径信息&#xff0c;通过路由可以确认转发IP报文的路径。 路由&#xff1a;是指路由器从一个接口上收到数据包&#xff0c;根据数据包的目的地址进行定向并转发到另一个接口的过程。 路由(routing)的定义是指分…

极简主义在UI设计中的应用及解析

极简主义&#xff0c;即“少就是多”。在设计中&#xff0c;极简主义是许多艺术概念之一&#xff0c;它描述了一种内容形式&#xff0c;可以在许多方面使用。现在移动UI界面和网页设计中的极简主义设计越来越多。即时设计认为&#xff0c;极简主义UI界面不仅美观&#xff0c;而…