Dijkstra算法
2022/2/26 22:51:22
本文主要是介绍Dijkstra算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
/* ------------------------------------------------- Author: wry date: 2022/2/26 21:56 Description: Dijkstra ------------------------------------------------- */ #include <bits/stdc++.h> using namespace std; const int MAXN = 200; struct Edge { int to; int length; Edge(int t,int l):to(t),length(l){} }; struct Point { int id; int distance; Point(int n,int d):number(n),distance(d){} bool operator< (Point p) const{ return distance>p.distance; //距离越小,优先级越高 } }; vector<Edge> graph[MAXN]; int dis[MAXN]; //表示起点到此测试点的最短距离 void Disjkstra(int start,int n) { fill(dis,dis+n,INT_MAX); dis[start] = 0; priority_queue<Point> myPriorityQueue; myPriorityQueue.push(Point(start,dis[start])); //存入第一个点,即它自己 while (!myPriorityQueue.empty()) { int p = myPriorityQueue.top().id; myPriorityQueue.pop(); for (int i=0;i<graph[p].size();i++) { //p _l_> q int q = graph[p][i].to; int l = graph[p][i].length; if (dis[p]+l<dis[q]) { //看是直接到q近还是经过p中转近 dis[q] = dis[p]+l; myPriorityQueue.push(Point(q,dis[q])); } } } } int main() { int n,m; while (cin>>n>>m) { memset(graph,0,sizeof(graph)); //初始化结构体的向量 while (m--) { int from,to,length; cin >> from >> to >> length; //Dijkstra应用于无向图 graph[from].push_back(Edge(to,length)); graph[to].push_back(Edge(from,length)); } int start,end; cin >> start >> end; Disjkstra(start,n); if (dis[end]==INT_MAX) { dis[end] = -1; } } return 0; }
这篇关于Dijkstra算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现