算法学习--Day9
2024-08-23 02:19:39
继上一次完成最小生成树后,这次我开始准备最短路径的程序。
最短路分为两种算法,第一个为Floyd算法,第二个为Dijkstra。
简单来说,Floyd是以点为参照对象,它使用三层循环求解当前图中所有点之间的最短距离。
也就是说,当他的循环处理结束后,你就可以从中找到任意两点之间的最短路径了。
他将大规模问题简化成为若干个子问题,并先对规模小的问题求解出最优值,之后利用规模小的问题的解去递推出大规模问题的解。
核心代码:
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
for(int k=;k<=n;k++){
if(ans[j][i]==- || ans[i][k]==-) continue;
//这句话说明倘若我j-i-k中间有某条路是不通的,这个时候我就不能被更新,所以直接跳过就好
if(ans[j][k]==- || ans[j][i]+ans[i][k]<ans[j][k]){ ans[j][k]= ans[j][i]+ans[i][k];}
//这句话用来更新最小值
}
}
}
下面我们看dijkstra算法。
题目描述
给你n个点,m条无向边,每条边都有长度d和花费p,给你起点s终点t,要求输出起点到终点的最短距离及其花费,如果最短距离有多条路线,则输出花费最少的。
输入描述:
输入n,m,点的编号是1~n,然后是m行,每行4个数 a,b,d,p,表示a和b之间有一条边,且其长度为d,花费为p。最后一行是两个数 s,t;起点s,终点t。n和m为0时输入结束。
(1<n<=1000, 0<m<100000, s != t)
输出描述:
输出 一行有两个数, 最短距离及其花费。
//
// Created by 陈平 on 2018/6/7.
// #include "iostream"
#include "stdio.h"
#include "vector"
using namespace std; struct E{
int next;
int c;
int cost; };
vector<E> edge[];
int dis[];
int cost[];
bool mark[];
int main(){
int n,m;
int s,t;
while (scanf("%d%d",&n,&m)!=EOF){
if(n== && m==n) break;
for (int i = ; i <=n ; ++i) {
edge[i].clear();
}
while (m--){
int a,b,c,cost;
cin>>a>>b>>c>>cost;
E tmp;
tmp.c = c;
tmp.cost = cost;
tmp.next = b;
edge[a].push_back(tmp);
tmp.next = a;
edge[b].push_back(tmp);
}
cin>>s>>t;
for (int j = ; j <=n ; ++j) {
dis[j] = -;
mark[j] = false;
}
dis[s] = ;
cost[s] = ;
mark[s] = true;
int newP = s; for (int k = ; k <n ; ++k) {
for (int i = ; i <edge[newP].size() ; ++i) { int t = edge[newP][i].next;
int c = edge[newP][i].c;
int co = edge[newP][i].cost;
if(mark[t]) continue;
if (dis[t]==- || dis[t]>dis[newP] + c ||dis[t]==dis[newP] + c && cost[t]>cost[newP]+co ){
dis[t] = dis[newP] + c;
cost[t] = cost[newP] + co;
}
} int minn = ;
for (int j = ; j <=n ; ++j) { if(mark[j]) continue;
if(dis[j]==-) continue;
if(dis[j] < minn ){ minn = dis[j];
newP = j; }
}
mark[newP] = true;
} cout<<dis[t]<<" "<<cost[t]<<endl;
}
}
在写最短路的时候,我们要熟悉使用链表的写法,当数据量增多的时候,使用链表会使节省空间与时间。所以我们要在初始化的时候使用push_back函数把值push进去。而在处理的时候,我们需要分两步去找最优解。第一步为更新当前点集合所连接的点的长度数据。(因为上一步加入了另一个点后我们的长度还未更新)第二步为寻找未在当前集合并且是最短距离的点。(具体流程见我之前的一个博客——https://www.cnblogs.com/Pinging/p/7911169.html)
最新文章
- linux的top命令参数详解
- Mysql空用户导致数据库登陆故障处理 (原创帖,转载请注明出处)
- css2----兼容----ie67的3像素bug
- iOS面试题汇总
- POJ 2785 4 Values whose Sum is 0(想法题)
- JSP 基础概念归纳 5分钟看完
- 自己编写php框架(一)
- javascript中怎么让一个页面执行多个window.onload?
- golang与C交互:cgo
- Delphi中实现MDI子窗体(转)
- python 深浅拷贝
- 二叉树Bynary_Tree(2):二叉树的递归遍历
- [POI2012]Odległość
- Java同步注解:@ThreadSafe、@Immutable、@NotThreadSafe、@GuardedBy
- Spring AOP中args()、arg-names、argNames
- 创成汇丨投脑风暴&#183;创心不止|路演日 第2期,寻IT创业者
- leetcode287
- mybatis 为什么要设置jdbcType
- Codeforces Round #368 (Div. 2) A. Brain&#39;s Photos 水题
- server的响应数据
热门文章
- The type List is not generic(转载)
- 自定义 spinner
- warez世界顶级压缩作品网站
- 【BZOJ2729】[HNOI2012]排队 组合数
- 【BZOJ2561】最小生成树 最小割
- EasyHLS实现将IPCamera摄像机的RTSP流转成HLS(ts+m3u8)直播输出
- 20170228 交货单过账增强 MV50AFZ1
- 给第三方apk进行系统签名的几种方式【转】
- css position弹性盒子测试
- Hihocoder #1095 : HIHO Drinking Game (微软苏州校招笔试)( *【二分搜索最优解】)