1、问题
一个求单源最短路径的问题。给定有向带权图 G =(V, E ),其中每条边的权是非负实数。此外,给定 V 中的一个顶点,
称为源点。现在要计算从源到所有其他各顶点的最短路径长
度,这里路径长度指路上各边的权之和。
2、分析
3、代码实现1、普通C++实现
#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];//下标表示当前节点值,然后值保