w****h 发帖数: 212 | 1 【 以下文字转载自 CS 讨论区 】
发信人: wmbyhh (wmbyhh), 信区: CS
标 题: 哪里可以找到关于Floyd-Warshall算法的图例?
发信站: BBS 未名空间站 (Thu Apr 24 17:23:57 2008)
对最短路径算法的Floyd-Warshall算法不是很懂,
想找个实例图解,
不知道哪里可以找到。 |
|
h**6 发帖数: 4160 | 2 我终于知道了,我得google onsite就fail在第一题上。
每相邻两项能得到一条rule,全部rule学会之后,需要根据传递性扩展rule生成一个
rule matrix
生成这个rule matrix有两个方法:
1.是用BFS或者DFS进行图的遍历
2.使用Floyd-Warshall算法。当时我在面试官面前Warshall说了半天,结果写出来成了
这样:
for(int i=0; i
for(int j=0; j
for(int k=0; k
if(rules[i][k] && rules[k][j])
rules[i][j] = 1;
看出错在哪里了吗,k应该在外层循环,结果我把他写到最内层去了。悔啊,没想到栽
这上面了。 |
|
m*****f 发帖数: 1243 | 3 Floyd Warshall算法, brute force解决贝 |
|
h**6 发帖数: 4160 | 4 写在前面:
昨天有私事麻烦done版务,来回折腾好几次。done版务始终尽心尽职,最终解决问题,
在此向他表达最诚挚的谢意。
历史回顾:
1.我从上大学才开始接触编程,最早学习的是谭浩强的《C语言程序设计》。当时啥也
不懂,只知道用最直接的方法实现问题,写个素数程序都可以执行几分钟。加之机时紧
张,常常在白纸上写好代码,上机调试,出错,再在草稿纸上修改,然后继续上机调试。
这期间写了算24、黑白棋、俄罗斯方块、模拟选课系统几个程序。
2.后来开始自学C++,买了张盗版VC,还经常去书店看白书。看的书主要分为两类,
Windows控件和C++语法。现在看起来觉得好笑,可惜当时被宏大空泛的书名所迷惑,其
实整本书只讲了怎样在对话框上添加几个按钮。由于对C的先入为主,我也一直认为C++
就是可以随处定义变量并有升级版struct的C。囫囵吞枣看下去的诸多概念也没有时间
消化运用。
这期间写了一些游戏的存档修改器和数据编辑器,写这类东西主要是寻找地址麻烦,找
到地址之后就剩一些累傻小子的活了。
至此为止,我所谓丰富的编程经验仅仅是一些依赖编译环境的编码和调试经验,虽然学
了很多数据结构和算法,... 阅读全帖 |
|
B*******1 发帖数: 2454 | 5 我的第一想法是
方法1:
根据矩阵建立一个adj matrix,
然后对每一个s,跑dijkstra,算到每一个a的最短距离,
对于每一个a,如果新的s算出来的最短距离更加小,就更新它的最短距离。
方法2:
建立adj matrix
跑flyoyd- warshal, 算每2点之间最短距离,
对每一个a,找到所有s的距离中最小的那一个。 |
|
y*******g 发帖数: 6599 | 6 其实我觉得Floyd–Warshall 并行应该没问题吧? |
|
y*******g 发帖数: 6599 | 7 DP?
是说Floyd–Warshall?
复杂度差的比较大吧
样 |
|
y*******g 发帖数: 6599 | 8 DP?
是说Floyd–Warshall?
复杂度差的比较大吧
样 |
|
i**d 发帖数: 357 | 9 这个可以用floyd-warshall来做吧。复杂度O(N^3) |
|
g**********y 发帖数: 14569 | 10 U just need to compute a table, char to char min cost.
Each char is a node.
First use warshall-Floyd to calc min cost between all nodes(from to) Then compute Min cost among pairs (they could go to a common node)
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
★ 发自iPhone App: ChineseWeb - 中文网站浏览器 |
|
p*****2 发帖数: 21240 | 11
我就学了Floyd-Warshall和Dijkstra。 还没碰到需要那个的题。有时间得看看。 |
|
p*****2 发帖数: 21240 | 12
因为Leetcode就是准备面试用的,不是玩竞赛的。对于面试来说,这题不是原题,原题
在CC150里。面试中遇到的也是CC150的原题。从算法和竞赛来讲,最短路径一般都是找
一条的,参见Dijkstra, 或者找所有pair的,参见Floyd-Warshall,但是所有pair也
是找最小cost而不是所有路径。另外每个pair只需要一个最短就可以了。因此word
ldadder II这题出的很诡异。既不是面试题,又不是竞赛题,我不知道有什么特别的意
义。
通常竞赛来说,输入的规模,时间,空间的要求都说的很详细。一般不需要写code就可
以把算法想的八九不离十,但是这题感觉就是要去死磕,我不太清楚,花那么多时间的
收获是什么。当然你要是觉得值得去做也没什么问题。我肯定不会花这个时间了。 |
|
p*****2 发帖数: 21240 | 13
因为Leetcode就是准备面试用的,不是玩竞赛的。对于面试来说,这题不是原题,原题
在CC150里。面试中遇到的也是CC150的原题。从算法和竞赛来讲,最短路径一般都是找
一条的,参见Dijkstra, 或者找所有pair的,参见Floyd-Warshall,但是所有pair也
是找最小cost而不是所有路径。另外每个pair只需要一个最短就可以了。因此word
ldadder II这题出的很诡异。既不是面试题,又不是竞赛题,我不知道有什么特别的意
义。
通常竞赛来说,输入的规模,时间,空间的要求都说的很详细。一般不需要写code就可
以把算法想的八九不离十,但是这题感觉就是要去死磕,我不太清楚,花那么多时间的
收获是什么。当然你要是觉得值得去做也没什么问题。我肯定不会花这个时间了。 |
|
|
h*****u 发帖数: 109 | 15 我感觉这个是one-to-all shortest path的变形。如果在坐标上有一个点s,距离的和
最小,等同于每个城市到s的shortest distance。
for s in all points
determine the sum of the shortest distances
output the minimum one
算shortest distances时,可以用all-pair shortest paths, such as Floyd-
Warshall |
|
y**********a 发帖数: 824 | 16 看起来更像 Floyd-Warshall,如果警察多的话。 |
|
y**********a 发帖数: 824 | 17 看起来更像 Floyd-Warshall,如果警察多的话。 |
|
y**********a 发帖数: 824 | 18 看起来更像 Floyd-Warshall,如果警察多的话。 |
|
y**********a 发帖数: 824 | 19 看起来更像 Floyd-Warshall,如果警察多的话。 |
|
r*****e 发帖数: 30 | 20 我的想法是把每个地铁站拆分成2个节点
一个节点表示在车上的状态,一个节点表示下车的状态
然后用Floyd warshall算
但是有些case不对 |
|
m********t 发帖数: 13072 | 21 下面我给出的list上的内容,都属于基本常识,无论对方考不考,你都应该了解优越性
和弱点的, 术语中文我不太会说
我脑海里能想到的(有很多我暂时没想起来的,不等于你就不该掌握了)
topological sorting
direct acyclic graph
relaxation method
floyd-warshall
Dijkstra's
Prim
Bellman-ford
Strongly/Weakly connected components
depth/breadth first search
Minimum spanning tree
and so on , heap, binary heap, B-tree, BST, linked-list
所有这些东西,无论考不考,你都该已经知道了,才可以预约面试
刷题是没什么本质性作用的,你刷了200多道题,很可能都是tree structure的,其他
部分没刷到,就傻眼了
除此之外,你要掌握scheduling的相关知识,
然后再去学一些常见的机器语言,C++或者java,这才是正确的学习顺序
一上来就用IDE/eclip... 阅读全帖 |
|
q*x 发帖数: 683 | 22 装蒜没你这摸装的. 随便挑你LIST几个
relaxation method
floyd-warshall
Bellman-ford
Strongly/Weakly connected components
就这些普通面试用不到, 高级码工也用不到. 你连码工面试都没搞过, 别装蒜丢人了. |
|
z*********n 发帖数: 1451 | 23
topological sort面试还考,但感觉现在面试连dijkstra和floyd warshall都不要求掌
握了,这也是本科教科书知识吧。上回面某家,面试官问了个带权值最短路径,我一听
虎躯一震,居然真会问dijkstra,抡起袖子就打算开搞,结果被面试官大声喝止,说你
讲讲思路,证明一下这个算法正确性就行了,不用写code,我还有点小失望呢。 |
|
r*****s 发帖数: 1815 | 24 。。。。
我面微软的时候也是
面试官问了个超简单的bfs最短路 然后问我有权怎么办
我刚要写他说算了
: topological sort面试还考,但感觉现在面试连dijkstra和floyd warshall都不
要求掌
: 握了,这也是本科教科书知识吧。上回面某家,面试官问了个带权值最短路径,
我一听
: 虎躯一震,居然真会问dijkstra,抡起袖子就打算开搞,结果被面试官大声喝止
,说你
: 讲讲思路,证明一下这个算法正确性就行了,不用写code,我还有点小失望呢。
|
|
s*******y 发帖数: 558 | 25 邻接矩阵表示的无向图 常见的warshall算法是O(n^3), where n is
the number of nodes.
有没有更快一点的算法呢?
谢谢 |
|
l*****g 发帖数: 49 | 26 well studied problem, huge literature
google "all pairs shortest path" or "Floyd–Warshall algorithm"
or "Johnson's algorithm" or read an algorithms textbook ... |
|
a***n 发帖数: 404 | 27 这个Floyd 是n^3, 复杂度跟 类Dijkstra算法一样的,太高了。
不知道有没有稍微好一点的,看了Floyd-Warshall改进版好像也是差不多这个量级的。
没办法,图太大了。埃。。。
刚刚google了下,貌似 n^3很难突破,就 Johnson 稍微算最好了。。。
另外貌似我用的 《algorithm design》竟然没有提到 Johnson, 看来跟 Introduction
to algorithm 内容差别还是很大阿。。。
另外,如果已知要求的pair集合,貌似就很难决定哪种算法好了。因为很多算法都是
bottom-up的,这个对于求部分pair很不利阿。 |
|
m********t 发帖数: 13072 | 28 【 以下文字转载自 JobHunting 讨论区 】
发信人: moonlightt (月光妹妹), 信区: JobHunting
标 题: 忍不住了,说两句
发信站: BBS 未名空间站 (Tue Oct 14 18:09:43 2014, 美东)
下面我给出的list上的内容,都属于基本常识,无论对方考不考,你都应该了解优越性
和弱点的, 术语中文我不太会说
我脑海里能想到的(有很多我暂时没想起来的,不等于你就不该掌握了)
topological sorting
direct acyclic graph
relaxation method
floyd-warshall
Dijkstra's
Prim
Bellman-ford
Strongly/Weakly connected components
depth/breadth first search
Minimum spanning tree
and so on , heap, binary heap, B-tree, BST, linked-list
所有这些东西,无论考不考,你都该已经知道了,才可以预约面试
刷题是没什么本... 阅读全帖 |
|
q*x 发帖数: 683 | 29 装蒜没你这摸装的. 随便挑你LIST几个
relaxation method
floyd-warshall
Bellman-ford
Strongly/Weakly connected components
就这些普通面试用不到, 高级码工也用不到. 你连码工面试都没搞过, 别装蒜丢人了. |
|