贪心算法之最短路径问题（Dijkstra算法）

95 阅读 0 评论 63 点赞

我是靠谱客的博主神勇未来，这篇文章主要介绍贪心算法之最短路径问题（Dijkstra算法），现在分享给大家，希望可以做个参考。

1、问题

一个求单源最短路径的问题。给定有向带权图 G =(V, E ),
其中每条边的权是非负实数。此外,给定 V 中的一个顶点,
称为源点。现在要计算从源到所有其他各顶点的最短路径长
度,这里路径长度指路上各边的权之和。

2、分析

3、代码实现

1、普通C++实现

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <cstdio>
#include <stack>
#include <string>

using namespace std;

/*
一定要记得如果初始化矩阵的话，肯定需要一个变量保存长和宽的最大值，
如果看到权重的话，肯定是需要有个变量保存最大值的权重
*/

//城市的节点数目的最大值
const int MAX_CITY_NUM = 100;
//节点权值的最大值
const int MAX_POLICY = 1e7;
//初始化权重矩阵
int map[MAX_CITY_NUM][MAX_CITY_NUM];
//源点到各个顶点的最短具体数组
int dist[MAX_CITY_NUM];
//下标表示当前节点