算法学习笔记（7.7）-贪婪算法（Dijkstra算法-最短路径问题） - ToB企服应用市场:ToB评测及商务社交产业平台

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

复制代码