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

news/2024/7/7 10:22:46

目录

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}")


http://lihuaxi.xjx100.cn/news/2196323.html

相关文章

推荐使用优豆云免费云服务器、免费虚拟主机

推荐使用优豆云免费云服务器、免费虚拟主机

官网地址&#xff1a;https://www.udouyun.com 经济实惠&#xff1a;相较于其他云服务器提供商&#xff0c;优豆云服务器提供免费的云服务&#xff0c;对于一些预算有限的个人和初创企业来说&#xff0c;是一个不错的选择。操作便捷&#xff1a;优豆云服务器提供了Linux和Wind…
阅读更多...
C语言实现三角波生成

C语言实现三角波生成

C语言实现三角波生成 #include <stdio.h>#define SAMPLE_RATE 10000 // 采样率10kHz=10000Hz 对应100us=0.1ms #define UP_TIME 12.5 //上升时间12.5ms #
阅读更多...
计算机组成结构—IO方式

计算机组成结构—IO方式

目录 一、程序查询方式 1. 程序查询基本流程 2. 接口电路 3. 接口工作过程 二、程序中断方式 1. 程序中断基本流程 2. 接口电路 3. I/O 中断处理过程 三、DMA 方式 1. DMA 的概念和特点 2. DMA 与 CPU 的访存冲突 3. DMA 接口的功能 4. DMA 接口的组成 5. DMA 的…
阅读更多...
Docker基础篇之Docker常规软件安装

Docker基础篇之Docker常规软件安装

文章目录 1. 总体步骤2. 安装tomcat3. 安装Mysql4. 安装Redis 1. 总体步骤 安装软件的总体步骤如下所示&#xff1a; 搜索镜像拉取镜像查看镜像启动镜像停止容器移除容器 2. 安装tomcat docker hub上查找tomcat镜像 或者使用一下命令查找&#xff1a; docker search tomca…
阅读更多...
加密经济浪潮：探索Web3对金融体系的颠覆

加密经济浪潮：探索Web3对金融体系的颠覆

随着区块链技术的快速发展&#xff0c;加密经济正在成为全球金融领域的一股新的浪潮。而Web3作为下一代互联网的代表&#xff0c;以其去中心化、可编程的特性&#xff0c;正深刻影响着传统金融体系的格局和运作方式。本文将深入探讨加密经济对金融体系的颠覆&#xff0c;探索We…
阅读更多...
JavaScript的核心语法

JavaScript的核心语法

JavaScript JavaScript&#xff1a;JavaScript的组成&#xff1a;核心语法&#xff1a;Hello&#xff1a;变量&#xff1a;JS的基本数据类型&#xff1a;特殊点&#xff1a; 数组&#xff1a;流程控制语句&#xff1a;函数&#xff1a;函数的重载&#xff1a;函数的递归:预定义…
阅读更多...
C++ AVL树 详细讲解

C++ AVL树 详细讲解

目录 一、AVL树的概念 二、AVL树的实现 1.AVL树节点的定义 2.AVL树的插入 3.AVL树的旋转 4.AVL树的验证 三、AVL树的性能 四、完结撒❀ 一、AVL树的概念 二叉搜索树虽可以缩短查找的效率&#xff0c;但 如果数据有序或接近有序二叉搜索树将退化为单支树&#xff0c;查 …
阅读更多...
Alsa UCM

Alsa UCM

Alsa Use Case Manager&#xff08;用例管理器&#xff09;描述如何为某些用例&#xff08;如 “播放音频”、“通话”&#xff09;设置 mixer 混频器。它还描述如何修改 mixer 混频器状态以将音频路由到某些输出和输入&#xff0c;以及如何控制这些设备。 这基本上涵盖了 Pul…
阅读更多...
最新文章

Copyright @ 2022~2023