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
就这些普通面试用不到, 高级码工也用不到. 你连码工面试都没搞过, 别装蒜丢人了. |
|
