欢迎辞欢迎来到“笃志以砺，决起而飞”！ 如果您是第一次来到本站，建议访问 本站导读以便更快地了解本站。 如果您喜欢本站， 欢迎订阅。 | 【本文由 Ceeji 原创，转载请注明出处并保留本注释。】 Bellman-Ford算法（根据发明者 Richard Bellman 和 Lester Ford 命名）是求解单源最短路径问题的一种算法。有时候这种算法也被称为 Moore-Bellman-Ford 算法，因为 Edward F. Moore 也为这个算法的发展做出了贡献。 单源点的最短路径问题是指：给定一个加权有向图G和源点s，对于图G中的任意一点v，求从s到v的最短路径。 与迪杰斯特拉算法，（另一种著名的求最短路径的算法）不同的是，在 Bellman-Ford 算法中，路径的权值可以为负数。 设想从我们可以从图中找到一个环路（即从v出发，经过若干个点之后又回到v）且这个环路中所有路径的权值之和为负。那么通过这个环路，环路中任意两点的最 短路径就可以无穷小下去。如果不处理这个负环路，程序就会永远运行下去。 而Bellman-Ford算法具有分辨这种负环路的能力。 算法描述 设G为加权有向图 V是所有结点的集合 E是所有路径的集合 S表示源点 n表示V中所有结点的数目 weight(u,v)表示从结点u到结点v的路径的权值。 Distanz(v)表示从源点s出发到结点v的最短路径的距离，（或者说是从s到v所有的路径中权值的最小值）。【Predecessor(v)表示节 点v的父结点。】在Bellman-Ford算法结束之后，可以输出，G是不是包含一个负环路。如果G不包含负环路，那么Distanz就存储了从s出发 到所有结点的距离。 Bellman-Ford 算法是 SPFA 算法的基础算法。SPFA 算法是 Bellman-Ford 算法的加强版，时间复杂度和适用面都优于 Dijkstra 算法。设G = (V,E,W) 为某一有向带权图（W 即 weight，权值），s，t 分别代表源点和终点，Distance(v) 代表 v 在算法当前阶段中暂定的从源点出发的最短权和，则算法的核心思想是进行至多 |V|-1 次的迭代处理，每次从 s 出发扩展一层路径，逐渐逼近最短路径。 [...] 对于大多数人来说，使用Microsoft SQL Server 或 Mysql 数据库可以方便地完成网络B/S,C/S软件的开发。但是，这是一个潜在的生产成本。Microsoft SQL Server和Mysql 的用于生产的版本不是免费的，更何况SQL Server的安装需要Microsoft Windows Server 系统的支持。 其实，完全可以自己动手、丰衣足食，开发出高效的网络应用开发平台，以便支持同时多用户多线程并发读写，并且只需要本地数据库支持，在这里我用 Access 做例子。 [...] 第一题：连续正整数（10分） 题目描述： 一个正整数有可能可以被表示为n(n>=2)个连续正整数之和，如： 15=1+2+3+4+5 15=4+5+6 15=7+8 请编写程序，根据输入的任何一个正整数，找出符合这种要求的所有连续正整数序列。 输入数据：一个正整数，以命令行参数的形式提供给程序。 输出数据：在标准输出上打印出符合题目描述的全部正整数序列，每行一个序列，每个序列都从该序列的最小正整数开始、以从小到大的顺序打印。如果结果有多个序列，按各序列的最小正整数的大小从小到大打印各序列。此外，序列不允许重复，序列内的整数用一个空格分隔。如果没有符合要求的序列，输出“NONE”。 例如，对于15，其输出结果是： 1 2 3 4 5 4 5 6 7 8 对于16，其输出结果是： NONE 评分标准： 程序输出结果是否正确。 原题：http://hi.baidu.com/astar/blog/item/69570fb35eedeba6d9335ab5.html 我见到的C++优化最好的代码的平均运行时间（若输入10000000）为0.15秒。 我设计的优化C#代码： ?View Code CSHARP1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 [...] 使用 C# 实现 Bin 类，快速方便地管理 byte[] 类型一直是我的心愿。因为在 C C++ C# VB 等语言中，byte[] 类型是常用的，但却没有太多方便的命令去处理它。因此我编写了 Bin 类。这个类实现了方便的管理，封装了大部分 Byte[] 操作，如添加、删除、查找等。在编写中注重速度、效率和方便性，支持索引器[index]直接引用，操作符重载等。 同时这也是我写的“ToEasy”C#简单化代码的一部分，namespace 就是 ToEasy 了！ 下面就是我写的代码： ?View Code CSHARP1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 [...] | |
近期评论