西安做网站哪家最便宜,网站建设代理合同,wordpress生成分类目录,鹤壁高端网站建设迪杰斯特拉算法
算法说明
迪杰斯特拉算法用来求解某一个起点到以其他所有点为终点的最短路径长度#xff1b;
算法思路-贪心算法
以下图为例 指定一个节点(即起点#xff09;#xff0c;例如计算“A”到其他节点的最短路径#xff1b;引入两个集合#xff08;S,U…迪杰斯特拉算法
算法说明
迪杰斯特拉算法用来求解某一个起点到以其他所有点为终点的最短路径长度
算法思路-贪心算法
以下图为例 指定一个节点(即起点例如计算“A”到其他节点的最短路径引入两个集合S,US集合包含所有已经求出其最短路径的点以及其最短长度U集合包括未求出的最短路径的点 所有和起点A直接相连的节点更新其与A的距离为路径长度没有直接相连的设置为∞ 从U集合中找出距离起点s路径最短的点加入S集合例如第一步最小的为A-D距离为2更新U集合路径if(A-DD-(B、C、E))(B、C、E)就更新U 重复执行横线内两步直到所有的节点都被加到了集合U中
下面使用迪杰斯特拉算法处理上图
①选取起点为A首先刷新所有和A点直接通过边相连的点即B、D点将A-D置为2A-B置为4其他A-CA-E均为正无穷
算法代码
#include stdio.h
#include iostream
#include map
#include stack
#include vector
#include queue
#include algorithm
#include sstream
#include cstring
#include string.h
#include stdlib.h
#define N 100005
#define INF 2147483647
typedef long long ll;
using namespace std;
typedef struct Edge {ll to;ll wei;Edge() {to-1;weiINF;//初始都为不可达状态}
} E;
ll n,M,s;
vectorEm[N]; //邻接表
bool wh[N]; //集合U和Strue代表节点已经放入Sfalse表示还在U集合
ll dis[N]; //存放起点到节点的最短距离
ll cnt; //S集合元素个数
void Dijkstra(int s)
{wh[s]true;cnt;while (cnt!n) {int MinINF,Minindex-1;//开始找S集合中距离s最近的节点for (int i1; in; i) {if (!wh[i](dis[i]Min)) {Mindis[i];Minindexi;}}//此时找到了最小的边//将此节点放到S集合wh[Minindex]true;cnt;//更新U集合路径for (int i0; im[Minindex].size(); i) {dis[m[Minindex][i].to]min(m[Minindex][i].weidis[Minindex],dis[m[Minindex][i].to]);}}
}
int main()
{cinnMs;for (int i1; in; i) {if(is) {dis[s]0;} else {dis[i]INF;}}ll f,t,w;for (ll i1; iM; i) { //存储图 cinftw;int flag0;//有向图不双向 for (int j0; jm[f].size(); j) { //重边 if (m[f][j].tot) {m[f][j].weimin(w,m[f][j].wei);flag1;break;}}if (flag0) {E e;e.tot;e.weiw;m[f].push_back(e);}}//找到和起点直接相连的节点设置和起点直接相连的距离for (int i0; im[s].size(); i) {dis[m[s][i].to]m[s][i].wei;}Dijkstra(s);for (int i1; in; i) {if (is) {(i1)?cout0:cout 0;continue;}(i1)?coutdis[i]:cout dis[i];}
}上述算法即是最朴素的迪杰斯特拉算法需要注意的是算法考虑了顶点有重边的情况这是洛谷的题目要求的题目链接 P3371 【模板】单源最短路径弱化版
但对于没有优化的迪杰斯特拉算法题目的强化版就会直接TLE分析朴素的Dijkstra算法我们发现可以优化的点有
每次寻找U集合中dis中最小的元素时使用了遍历的方法但我们可以使用小顶堆保证每次直接弹出最小的值不需要再去遍历
对于优先队列使用stl库的priority_queue实现。
迪杰斯特拉算法的优缺点
优点 算法思路简单比较容易上手使用经典的最短路算法适合大多数场景 缺点 时间复杂度和其他算法相比不太理想适用于节点n不太多的情况不能处理存在总花费为负值且从源点S可达的环路的图因为显然无限兜圈子花费会越来越小事实上存在负环的情况是抓住了贪心算法的弱点导致问题不能解决
