。。。

singuloUID: 3181417

你毛毛啊 发表于 2015-10-29 05:15


Dijkstra的算法思想很基本就是Greedy，你如果上过数据结构和算法的话，应该知道可以用不同的数据结构来实现，而且有向图 无向图 无环 有环 甚至负环，很多不同的地方，最短路径不是你想的那么简单。

Dijkstra没负edge就行。有负edge没负环用bellman-ford, 有负环就没最短路径了。检测负环多跑一轮，移除负环是np-hard。所以说其实不难。

你毛毛啊UID: 3472861

singulo 发表于 2015-10-29 19:08
Dijkstra没负edge就行。有负edge没负环用bellman-ford, 有负环就没最短路径了。检测负环多跑一轮，移除负环 ...

对的，有负就是动态规划了

你毛毛啊UID: 3472861

wrath 发表于 2015-10-29 16:27
最短路径就不用考虑环了 毕竟是求最短路径 不会再里面瞎绕

主要是考虑negative edge，negative cycle, Dijkstra处理不了这种情况。

wrathUID: 2704440

你毛毛啊 发表于 2015-10-30 02:52
主要是考虑negative edge，negative cycle, Dijkstra处理不了这种情况。

嗯 不过那个作业没那么难 点给的是二维坐标 自己算距离 所以不存在负环

CharlesZhuoChenUID: 3542723

sekkgoodjob 发表于 2015-10-29 03:54
十分感谢大大....看起来好有意思.....python+ctype,我有朋友面在大多的广告竞价（RTB）也是考察的类似的数 ...

哈哈 不是大大~
我舍友就选了三门课，比我多了一门606算法。然后他现在每天基本2点钟左右睡觉，不过好像还是有精力撸一撸的，有助睡眠嘛

PharmacaceUID: 3617186

CharlesZhuoChen 发表于 2015-10-29 00:58
我是15 fall UW ECE 新生，提供些相关信息供你参考吧：
1. 课程难度：
我这学期专业课选了650 651， 加一 ...

额。。最短路径有木有时空要求啊。。SPFA行么还是要Heap+迪杰斯特拉。。请原谅我一看见题就兴奋。。

CharlesZhuoChenUID: 3542723

Pharmacace 发表于 2015-11-18 13:56
额。。最短路径有木有时空要求啊。。SPFA行么还是要Heap+迪杰斯特拉。。请原谅我一看见题就兴奋。。

没有时空要求，那个作业只是锻炼一下图的数据结构，算法用BFS就行了
不过新出的assignment4会要求将这个作业改成用SAT求顶点覆盖问题，然后在assignment5里面把assignment4改成多线程的。。。
目前做到assignment5了，感觉作业其实是小偏工程的，如果之前的代码鲁棒性和重用性好的话，后面的345就会轻松很多，否则如果前面的代码遗留下了一些小坑的话，会增加后面作业debug的工作量 xD

小雪同学UID: 3673323

说句题外话，你diploma毕业申请过PGWP吗，如果申请过一次，除非毕业前就能找到工作拿工签，要不你毕业后那什么身份找工作呢？