算法学习笔记(7.7)-贪心算法(Dijkstra算法-最短路径问题)

目录

1.最短路径问题

 2.Dijkstra算法介绍

 3.Dijkstra算法演示

4.Dijkstra算法的代码示例


1.最短路径问题

图论中的一个经典问题,通常是指在一个加权图中找到从一个起始顶点到目标顶点的最短路径。

  1. 单源最短路径问题:给定一个加权图和一个起始顶点,要找到从该起始顶点到图中所有其他顶点的最短路径。

    • Dijkstra算法:适用于没有负权边的图,能够找到单源最短路径。

    • Bellman-Ford算法:适用于存在负权边的图,能够找到单源最短路径。

  2. 全源最短路径问题:给定一个加权图,要找到图中任意两个顶点之间的最短路径。

    • Floyd-Warshall算法:适用于有向图或无向图,能够找到所有顶点之间的最短路径。
  3. 最短路径问题的应用

    • 在网络路由中,确定数据包的最佳路径。

    • 在地图应用程序中,找到两个地点之间的最短驾驶路径。

    • 在交通规划中,优化公交线路或货运路径。

    • 在电路设计中,找到电路中信号传输的最短路径。

  4. 解决最短路径问题的算法

    • Dijkstra算法:适用于非负权重的图,能够找到单源最短路径。

    • Bellman-Ford算法:适用于存在负权重的图,能够找到单源最短路径。

    • A*算法:一种启发式搜索算法,用于寻找从起点到目标点的最短路径。

    • Bellman-Ford算法:适用于有向图或无向图,能够找到所有顶点之间的最短路径。

 2.Dijkstra算法介绍

1.Dijkstra算法特点:

迪科斯彻算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题,算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。

2.Dijkstra算法的步骤:

2.1 初始化:创建一个空的集合用于存储已经找到最短路径的顶点,以及一个数组用于存储从起始顶点到每个顶点的最短距离。将起始顶点的最短距离设置为0,其他顶点的最短距离设置为无穷大。

2.2 选取起始顶点:将起始顶点加入集合,更新起始顶点到相邻顶点的最短距离。

2.3 重复步骤:重复以下步骤,直到所有顶点都被加入集合为止:
   2.3.1 从未加入集合的顶点中选取与起始顶点距离最短的顶点加入集合。
   2.3.2 更新该顶点到相邻顶点的最短距离,如果经过该顶点到相邻顶点的距禒小于已知的最短距离,则更新最短距离。

2.4 最终结果:当所有顶点都被加入集合后,最短路径就被找到了。

3. Dijkstra算法的特点和适用性:

3.1 Dijkstra算法适用于带权重的有向图或无向图。
3.2 该算法保证找到的路径是最短的,但前提是图中不能有负权重的边
3.3 时间复杂度取决于具体实现,通常在稠密图上的时间复杂度为O(V^2),在稀疏图上的时间复杂度为O(E * log V)。
3.4 Dijkstra算法常用于路由算法、网络分析、地图应用等领域。

4. Dijkstra核心算法思想:

迪杰斯特拉算法主要特点是从起始点开始,采用贪心算法的策略,每次遍历到始点距离最近且未访问过的顶点的邻接节点,直到扩展到终点为止

 3.Dijkstra算法演示

1.用一个 dist 数组保存源点到其余各个节点的距离,dist[i] 表示源点到节点 i 的距离。初始时,dist 数组的各个元素为无穷大。用一个状态数组 state 记录是否找到了源点到该节点的最短距离,state[i] 如果为真,则表示找到了源点到节点 i 的最短距离,state[i] 如果为假,则表示源点到节点 i 的最短距离还没有找到。初始时,state 各个元素为假。

2.源点到源点的距离为 0。即dist[1] = 0。

3.遍历 dist 数组,找到一个节点,这个节点是:没有确定最短路径的节点中距离源点最近的点。假设该节点编号为 i。此时就找到了源点到该节点的最短距离,state[i] 置为 1。

4.遍历 i 所有可以到达的节点 j,如果 dist[j] 大于 dist[i] 加上 i -> j 的距离,即 dist[j] > dist[i] + w[i][j](w[i][j] 为 i -> j 的距离) ,则更新 dist[j] = dist[i] + w[i][j]。

5.重复 3 4 步骤,直到所有节点的状态都被置为 1。


6.此时 dist 数组中,就保存了源点到其余各个节点的最短距离。

4.Dijkstra算法的代码示例

//c++代码实现
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 510, M = 100010, INF = 0x3f3f3f3f;

int h[N], e[M], ne[M], w[M], idx;
//h数组用来储存每个边链表的头部
//e数组用来存储每条边指向的节点编号
//w用来存储每条边的权重
//ne数组用来实现邻接表中的链表结构 
int dist[N]; //state 记录是否找到了源节点到该节点的最短距离
bool state[N]; //dist 数组保存源点到其余各个节点的距离
int n, m; //图的节点个数和边数
int adjMatrix[N][N];  // 邻接矩阵

void add(int a, int b, int c) 
{
	e[idx] = b ; //将当前边的目标节点b存储在,e[idx]中 
	w[idx] = c ; //将该条边的权重存储在,w[idx]中 
	ne[idx] = h[a] ; //更新ha将之前节点a的第一条边的索引存储在ne数组,使其一直处于更新状态指向最新的一条边 
	h[a] = idx++ ;	
}

// 打印邻接表
void printAdjList() {
    for (int i = 1; i <= n; ++i) {
        cout << "Vertex " << i << ":";
        for (int j = h[i]; j != -1; j = ne[j]) {
            cout << "-> (" << e[j] << ", " << w[j] << ")";
        }
        cout << endl;
    }
}

// 创建并打印邻接矩阵
void printAdjMatrix() {
    // 初始化邻接矩阵
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (i == j) adjMatrix[i][j] = 0;
            else adjMatrix[i][j] = INF;
        }
    }
    
    // 填充邻接矩阵
    for (int i = 1; i <= n; ++i) {
        for (int j = h[i]; j != -1; j = ne[j]) {
            int to = e[j];
            adjMatrix[i][to] = min(adjMatrix[i][to], w[j]);  // 如果有重边,保留权重最小的一条
        }
    }
    
    // 打印邻接矩阵
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (adjMatrix[i][j] == INF) cout << "INF ";
            else cout << adjMatrix[i][j] << " ";
        }
        cout << endl;
    }
}

void Dijkstra()
{
	memset(dist, 0x3f, sizeof(dist)) ; //dist 初始化数组中的元素为最大值
	dist[1] = 0 ;
	for (int i = 0 ; i < n ; i++)
	{
		int t = -1 ;
		for (int j = 1 ; j <= n ; j++)
		{
			//遍历 dist 数组,找到没有确定最短路径的节点 
			if (!state[j] && (t == -1 || dist[j] < dist[t]))
			{
				t = j ;	
			}
		}
		state[t] = 1 ; //将该位置置为访问
			
		for (int j = h[t]; j != -1 ; j = ne[j]) //遍历 t 所有可以到达的节点i 
		{
			int i = e[j] ;
			dist[i] = min(dist[i], dist[t] + w[j]) ; //更新dist[j] 
		}	
			
	} 
}

int main()
{
	memset(h, -1, sizeof(h)) ;
	
	cin >> n >> m ;
	while (m--)
	{
		int a, b, w ;
		cin >> a >> b >> w ;
		add(a, b, w) ;
	}
	Dijkstra() ;
	if (dist[n] != 0x3f3f3f3f)
	{
		cout << dist[n] ;
	}
	else
	{
		cout << "-1" ;
	}
	// 打印邻接表
    printAdjList();
    // 创建并打印邻接矩阵
    printAdjMatrix();
	return 0 ;
}

#python代码示例

# 简单的Dijkstra算法
import heapq

def dijkstra(graph, start) :
    # 初始化距离字典,将所有节点的距离设置为无穷大
    distances = {node : float('inf') for node in graph}
    # 源节点到自身的距离设置为0
    distances[start] = 0
    # 使用优先队列来进行优化,队列中的元素(距离,节点)
    priority_queue = [(0,start)]

    while priority_queue :
        # 弹出队列中最小距离的节点
        current_distance, current_node = heapq.heappop(priority_queue)
        # 如果弹出的节点距离大于当前记录的距离,则忽略(已找到更短路径)
        if current_distance > distances[current_node] :
            continue
        # 遍历相邻的节点,更新距离
        for neighbor, weight in graph[current_node].items() :
            distance = current_distance + weight
            # 如果通过当前节点到达相邻节点的距离更短,则更新距离字典和最小堆
            if distance < distances[neighbor] :
                distances[neighbor] = distance
                heapq.heappush(priority_queue,(distance,neighbor))
                print(f"更新节点: {neighbor} 的最短路径为: {distance}")
    return distances

graph = {
'A': {'B': 1, 'C': 3},
'B': {'A': 1, 'C': 1, 'D': 4},
'C': {'A': 3, 'B': 2, 'D': 1},
'D': {'B': 4, 'C': 1}
}
start = 'A'
# print(dijkstra(graph, start))  # {'A': 0, 'B': 1, 'C': 3, 'D': 4}

shortest_paths = dijkstra(graph, start)
print("\n从节点 {} 到图中其他节点的最短路径:".format(start))
for node, distance in shortest_paths.items():
    print(f"到节点 {node} 的最短距离是: {distance}")

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

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

相关文章

AI三巨擘或面临反垄断审查 | 百能云芯

据纽约时报与路透社披露&#xff0c;有内部消息人士指出&#xff0c;美国的相关监管机构已达成共识&#xff0c;计划对OpenAI、微软及英伟达在人工智能&#xff08;AI&#xff09;领域的领导地位展开反垄断审查。这一动作被视为AI监管力度加强的明显信号。 根据此项共识&#x…

matlab 计算三维空间点到直线的距离

目录 一、算法原理二、代码实现三、结果展示四、参考链接本文由CSDN点云侠原创,原文链接。如果你不是在点云侠的博客中看到该文章,那么此处便是不要脸的爬虫与GPT。 一、算法原理 直线的点向式方程为: x − x 0 m = y

海康威视综合安防管理平台 多处 FastJson反序列化RCE漏洞复现

0x01 产品简介 海康威视综合安防管理平台是一套“集成化”、“智能化”的平台,通过接入视频监控、一卡通、停车场、报警检测等系统的设备。海康威视集成化综合管理软件平台,可以对接入的视频监控点集中管理,实现统一部署、统一配置、统一管理和统一调度。 0x02 漏洞概述 由于…

XR和Steam VR项目合并问题

最近有一个项目是用Steam VR开发的&#xff0c;里面部分场景是用VRTK框架做的&#xff0c;还有一部分是用SteamVR SDK自带的Player预制直接开发的。 这样本身没有问题&#xff0c;因为最终都是通过SteamVR SDK处理的&#xff0c;VRTK也管理好了SteamVR的逻辑&#xff0c;并且支…

【YOLOV8】4.图片分类-训练自己的数据集

Yolo8出来一段时间了,包含了目标检测、实例分割、人体姿态预测、旋转目标检测、图像分类等功能,所以想花点时间总结记录一下这几个功能的使用方法和自定义数据集需要注意的一些问题,本篇是第四篇,图像分类功能,自定义数据集的训练。 YOLO(You Only Look Once)是一种流行的…

【生产排查】解决 Kettle 没有运行日志的问题

文章目录 背景排查解决第 1 步:修改 kettle-service.conf,添加日志配置第 2 步:使用最新配置文件重启 kettle第 3 步:验证日志配置是否生效背景 🚀 项目使用 Kettle 作为 ETL 工具,从外部系统中抽取数据、转换数据、并最终加载到本项目的数据库中。 😂 存在的问题:据…

Vue3【十】07使用ref创建基本类型的响应式数据以及ref和reactive区别

Vue3【十】07使用ref创建基本类型的响应式数据以及ref和reactive区别 ref 也可以创建对象类型的响应式数据&#xff0c;不过要使用.value ref 处理对象数据的时候&#xff0c;底层数据还是reactive格式的 reactive 重新分配一个新对象&#xff0c;会失去响应式可以使用Object.a…

重生奇迹MU格斗家技能

格斗家有9个技能&#xff0c;其中幽冥青狼拳.斗气爆裂拳.神圣气旋.这3个是武器上带的技能。 回旋踢.幽冥光速拳.炎龙拳.这3个是买羊皮纸学的技能&#xff08;回旋踢是格斗最强技能&#xff09;。 还有3个给自己加BUFF的技能&#xff0c;斗神破&#xff08;增加无视防御的状态&…

Linux lvm卷扩容之SSM

介绍 SSM&#xff08;System Storage Manager&#xff09;是系统存储管理器&#xff0c;它是一种统一的命令行界面&#xff0c;用于管理各种存储设备。通过SSM&#xff0c;用户可以方便地管理、配置和监控存储系统。检查关于可用硬驱和LVM卷的信息。显示关于现有磁盘存储设备、…

专为Mac设计的窗口管理Magnet 中文

Magnet是一款专为Mac设计的窗口管理工具软件。它具备强大的多窗口管理能力&#xff0c;支持用户通过简单的拖放操作&#xff0c;将应用程序窗口快速对齐、排列和分组。此外&#xff0c;Magnet还提供了预设的布局选项和自定义设置功能&#xff0c;帮助用户实现个性化的窗口布局。…

Html/HTML5常用标签的学习

课程目标 项目实战&#xff0c;肯定就需要静态网页。朝着做项目方式去学习静态网页。 01、编写第一个html工程结构化 cssjsimages/imgindex.html 归档存储和结构清晰就可以。 02、HTML标签分类 认知&#xff1a;标签为什么要分类&#xff0c;原因因为&#xff1a;分门别类…

【java】速度搭建一个springboot项目

使用软件&#xff1a;IDEA&#xff0c;mysql 使用框架&#xff1a;springboot mybatis-plus druid 坑点 使用IDEA搭建一个springboot项目的时候&#xff0c;需要考虑一下IDEA版本支持的JDK版本以及maven版本。否则再构建项目&#xff0c;引入pom的时候就会报错。 需要检查…

Tongweb7重置密码优化版*(by lqw )

如图所示&#xff0c;输入初始密码是会报错的&#xff0c;说明已经修改了密码 首先我们先备份一下tongweb的安装目录&#xff0c;避免因为修改过程中出现的差错而导致tongweb无法启动&#xff1a; 备份好了之后&#xff0c;我们关闭掉tongweb。 方式一&#xff1a; Cd 到tong…

近期面试HW中级蓝问题(非常详细)零基础入门到精通,收藏这一篇就够了

01 — HW问题 1.sqlmap拿shell的原理&#xff0c;需要什么条件&#xff0c;–os-shell的原理 2.冰蝎的流量特征 3.哥斯拉的流量特征 4.如果判断一个web是s2写的 5.fastjson了解嘛&#xff1f;Log4j了解嘛&#xff1f;如何在流量中发现Log4j的攻击特征 6.HW前的准备工作…

【爬虫】使用Python爬取百度学术页面的标题、作者、摘要和关键词

目录 安装所需库编写爬虫代码解释运行脚本结果 在本文中&#xff0c;我将介绍如何使用Python编写一个网络爬虫&#xff0c;从百度学术页面提取研究论文的标题、作者、摘要和关键词。我们将使用 requests和 BeautifulSoup库来实现这一目标。 安装所需库 首先&#xff0c;确保…

【Python错误】:AttributeError: ‘generator‘ object has no attribute ‘next‘解决办法

【Python错误】&#xff1a;AttributeError: ‘generator’ object has no attribute next’解决办法 在Python中&#xff0c;生成器是一种使用yield语句的特殊迭代器&#xff0c;它允许你在函数中产生一个值序列&#xff0c;而无需一次性创建并返回整个列表。然而&#xff0c;…

为什么说组合优于继承?

在编程中&#xff0c;继承和组合是用于在面向对象语言中设计和构建类和对象的两种基本技术。 继承&#xff0c;它允许一个类&#xff08;称为派生类或子类&#xff09;从另一个类&#xff08;称为基类或超类&#xff09;继承属性和行为。换句话说&#xff0c;子类“是”超类的…

防汛应急排涝泵车的特点,有哪些用途

一、产品概述 移动柴油水泵机组又称移动拖车泵&#xff0c;它采用柴油作为燃料&#xff0c;通过内燃机的工作原理将化学能转化为机械能&#xff0c;进而驱动水泵进行抽水或输送任务。这种机组广泛应用于消防、市政应急给水、农业灌溉、防洪抢险等多个领域&#xff0c;其灵活性…

Pyinstaller安装与使用

一、Pyinstaller简介 PyInstaller将Python应用程序冻结(打包)独立可执行文件中。它可以构建较小的可执行文件,它是完全多平台的,并且使用OS支持来加载动态库,从而确保完全兼容。 二、Pyinstaller安装 1、下载安装 首先安装“pip install pywin32” 其次“pip install …

从GPT-4提取关键特征:Extracting Concepts from GPT-4

大家好,我是木易,一个持续关注AI领域的互联网技术产品经理,国内Top2本科,美国Top10 CS研究生,MBA。我坚信AI是普通人变强的“外挂”,所以创建了“AI信息Gap”这个公众号,专注于分享AI全维度知识,包括但不限于AI科普,AI工具测评,AI效率提升,AI行业洞察。关注我,AI之…