duganlx

分类

8051单片机(1) Android(4) dsp(4) linux(6) Qt(2) stc(1) 未归档(7) 算法相关(58)

/ 注册

全部文章（共83篇）

Bellman-Ford算法的队列优化及邻接表

Bellman-Ford算法原始版本中，在每次实施一次松弛操作后，就会有一些顶点已经求得其最短路，此后这些顶点的最短路的估计值就会一直保持不变，不再受后续松弛操作的影响，但是每次还要判断是否需要松弛，这里浪费了时间。这就启发我们：每次仅对最短路估计值发生变化的顶点的所有出边执行松弛操作。 ...

2019-12-20

0 515

Bellman-Ford算法

解决负权边 //假设1号顶点为源点核心算法: for(int k=1;k<=n-1;k++) //进行n-1轮松弛 for(int i=1;i<=m;i++) //枚举每一条边 if( dis[ v[i] ] > dis[ u[i] ] + w...

2019-12-20

0 562

Dijkstra算法

算法的基本思路：每次找到离源点最近的一个顶点，然后以该顶点为中心进行扩展，最终得到源点到其余所有点的最短路径基本步骤： 1.将所有的顶点分为两部分：已知最短路程的顶点集合P和未知最短路径的顶点集合Q。最开始，已知最短路径的顶点集合P中只有源点一个...

2019-12-20

1 548

Floyd算法

/* * 算法基本思想： * 最开始只允许进过1号顶点进行中转，接下来只允许进过1和2号 * 顶点进行中转...，允许经过1~n号所有顶点进行中转，求任意两 * 点之间的最短路程。 * * input n=4,m=8 -->4个城市，8条公路 * t1 t2 t3 -->...

2019-12-20

0 425

最短路径算法--Til the Cows Come Home

Til the Cows Come Home Bessie is out in the field and wants to get back to the barn to get as much sleep as possible before Farmer John wakes her for...

2019-12-20

0 576

最短路径算法--最短路

最短路在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？ Input 输入包括多组数据。每组数据第一行是两个整数N、M（N<=...

2019-12-20

0 522

最短路径算法--最短路径问题

最短路径问题给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。 Input 输入n,m，点的编号是1~n,然后是m行，每行4个数 a,b,d,p，表示a和b之间有一条边，且其长度为d，花费为p。...

2019-12-20

0 649

最短路径算法--Cow Contest

Cow Contest N (1 ≤ N ≤ 100) cows, conveniently numbered 1..N, are participating in a programming contest. As we all know, some cows code better than ...

2019-12-20

0 649

最短路径算法--HDU Today

HDU Today 经过锦囊相助，海东集团终于度过了危机，从此，HDU的发展就一直顺风顺水，到了2050年，集团已经相当规模了，据说进入了钱江肉丝经济开发区500强。这时候，XHD夫妇也退居了二线，并在风景秀美的诸暨市浬浦镇陶姚村买了个房子，开始安度晚年了。这样住了一段时间，徐总对当地的交通还...

2019-12-20

0 660

dfs/bfs--Red and Black

Red and Black There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. Fr...

2019-12-20

0 463