n****y
发帖数: 106 | 1 最近碰到一个问题，关于dijkstra的，呵呵
dijkstra是用来解决最短路径的，graph上面只有一种weight,比如distance,找到一个
从source到destination的最短路径
现在有个问题就是，假设graph上每条edge都有两种weight,say distance and time,
现在要
用一种算法也是minimize 的distance, 但是subject to total time < T
也就是说，原来的dijkstra找出的路径可能不行了，因为总时间可能>T
我看了点文献，这个问题是NP-Hard, 有一些用heuristic来减少complexity的
谁能推荐个比较经典的算法，不需要性能最好，保证对的就可以了。刚看了一个“专利
”，研究到最后发现根本就是错的，sigh.
多谢。 |
|
n****y
发帖数: 106 | 2 最近碰到一个问题，关于dijkstra的，呵呵
dijkstra是用来解决最短路径的，graph上面只有一种weight,比如distance,找到一个
从source到destination的最短路径
现在有个问题就是，假设graph上每条edge都有两种weight,say distance and time,
现在要
用一种算法也是minimize 的distance, 但是subject to total time < T
也就是说，原来的dijkstra找出的路径可能不行了，因为总时间可能>T
我看了点文献，这个问题是NP-Hard, 有一些用heuristic来减少complexity的
谁能推荐个比较经典的算法，不需要性能最好，保证对的就可以了。刚看了一个“专利
”，研究到最后发现根本就是错的，sigh.
多谢。 |
|
n****y
发帖数: 106 | 3 最近碰到一个问题，关于dijkstra的，呵呵
dijkstra是用来解决最短路径的，graph上面只有一种weight,比如distance,找到一个
从source到destination的最短路径
现在有个问题就是，假设graph上每条edge都有两种weight,say distance and time,
现在要
用一种算法也是minimize 的distance, 但是subject to total time < T
也就是说，原来的dijkstra找出的路径可能不行了，因为总时间可能>T
我看了点文献，这个问题是NP-Hard, 有一些用heuristic来减少complexity的
谁能推荐个比较经典的算法，不需要性能最好，保证对的就可以了。刚看了一个“专利
”，研究到最后发现根本就是错的，sigh.
多谢。 |
|
r*********m
发帖数: 100 | 4 Edsger Dijkstra, creator of much of the discipline of computer programming,
is dead, but his legacy lives on in every computer
Edsger Wybe Dijkstra, one of the creators of the art and science of computer
programming, has died. Born in Rotterdam in 1930, his career in Europe and
America included some of the first computer simulations in aviation and arch
itecture. A background in mathematics and science -- his mother was a mathem
atician, his father a chemist -- led to his applying similar discip |
|
h***n
发帖数: 1275 | 5 的确很搞笑，dijkstra 算法的那个证明的确是证明，不过可发一笑 |
|
|
h***n
发帖数: 1275 | 7 的确很搞笑，dijkstra 算法的那个证明的确是证明，不过可发一笑 |
|
|
p*****2
发帖数: 21240 | 9
多谢。不知道问什么这道题出在了TC的DP tutorial里。Dijkstra应该是Greedy. |
|
|
|
f*******n
发帖数: 12623 | 12 starts like English word "dike"
dike stra
Dijkstra is Dutch. "ij" is one letter in Dutch and it's the same as "y" |
|
w****x
发帖数: 2483 | 13 1 function Dijkstra(Graph, source):
2 for each vertex v in Graph:
3 dist[v] := infinity ;
4
5 previous[v] := undefined ;
6
7
8 dist[source] := 0 ;
9 Q := the set of all nodes in Graph ; ... 阅读全帖 |
|
m********l
发帖数: 791 | 14 或者替他题目用dijkstra's algorithm的？
想看看有没有比较interview friendly的解法（数据结构的实现简单一些）
主要针对edge weighted digraph的题目
谢谢！ |
|
p*****2
发帖数: 21240 | 15
想练习的话，BFS都可以用dijkstra写一遍。 |
|
m********l
发帖数: 791 | 16 谢谢提示
dijkstra一般的implementation感觉就是BFS+PriorityQueue
我想问的是一般大家如何定义一个Edge class和PriorityQueue里面的Comparator
谢谢 |
|
m*******n
发帖数: 6660 | 17 LP也在看算法，有个算法叫Dijkstra's Algorithm, 她不会念那个奇怪的单词。
我一下就给她念出来了。她很好奇为什么这么奇怪的名字我会念。我看看我吃灰的
Witcher3，笑而不语。 |
|
R******k
发帖数: 4756 | 18 哈哈，你不是搞艺术的吗，居然还知道 Dijkstra, 刮目相看啊~ |
|
h*********n
发帖数: 915 | 19 【 以下文字转载自 JobHunting 讨论区 】
发信人: heavyburden (nothing), 信区: JobHunting
标 题: Dijkstra SSSP@CLR的疑问
发信站: BBS 未名空间站 (Fri Dec 14 12:07:54 2007)
这个算法基本想法是用一个优先队列，每次取最小的节点，然后修改相邻节点的key。
直到队列为空。
我的疑问是，在修改了相邻节点之后，优先队列的性质已经无法保持了。比如如果是用
堆实现的优先队列，那么修改过key之后需要重新建堆才行。
但是这一步在哪里完成呢？算法里没有，在extractMin里？但这本书上关于堆的
extractMin是先取最小值，再重建堆。当然，可以额外加一步，在取最小值之前多建一
次堆也不影响复杂度。但是这样对通用的堆操作来说效率不高。
有哪位牛牛能解释解释？ |
|
r****y
发帖数: 26819 | 20 果然是穿越过来的机器人。Dijkstra十年前就去世了。
atom |
|
d****n
发帖数: 1637 | 21 Edsger Wybe Dijkstra (Dutch pronunciation: [ˈɛtsxər ˈwib
ə ˈdɛikstra] ( listen); May 11, 1930 – August 6, 2002) was a
Dutch computer scientist. He received the 1972 Turing Award for fundamental
contributions to developing programming languages, and was the Schlumberger
Centennial Chair of Computer Sciences at The University of Texas at Austin
from 1984 until 2000. |
|
S**I
发帖数: 15689 | 22 BF和Dijkstra类似，单靠这个解决不了LZ的问题；因为每个edge有两个weight
away. |
|
t********r
发帖数: 4908 | 23 ☆─────────────────────────────────────☆
littleice (家有两宝：狗娃猪仔) 于 (Sat Apr 10 15:27:51 2010, 美东) 提到:
刚看了Outliers的后记，原来作者的外婆是个推外婆啊，:D
☆─────────────────────────────────────☆
flyinger (上香上香) 于 (Sat Apr 10 16:12:42 2010, 美东) 提到:
u r so fast
I am still in the process of paying at dangdang
dont know why my credit card payment failed
☆─────────────────────────────────────☆
Netstea (冰茶) 于 (Sat Apr 10 17:44:23 2010, 美东) 提到:
在当当买东西，用amex card付款比较好用
☆─────────────────────────────────────☆
... 阅读全帖 |
|
f*******y
发帖数: 988 | 24 发信人: RuralHunter (乡村猎人), 信区: Programming
标 题: 看看牛人们是怎么评价编程语言的zz
发信站: 水木社区 (Tue May 22 11:33:20 2012), 站内
Basic
一个有过 BASIC 编程经历的人是很难学会好的编程习惯的。作为一个潜在的程序员
，他们已经被脑残并且无法修复。
-- Edsger Wybe Dijkstra，Dijkstra 算法发明者
C
C 语言程序就像一群拿着刀的人在刚刚打过蜡的地板上快速的跳舞。
-- Waldi Ravens
罗马帝国衰败的主要原因之一是因为他们缺少0，他们没有办法知道他们的 C 程序
已经成功的执行完了。
-- Robert Firth
现在是早上五点，你知道那个指针现在什么地方吗？
-- 匿名
C++
C 很容易让你朝自己的脚开枪。在 C++ 中，这么做变的困难了，但是你要不注意就
会崩掉自己的整条腿。
-- Bjarne Stroustrup，C++ 发明者
我发明了“面向对象”，... 阅读全帖 |
|
g***s
发帖数: 3811 | 25 dijkstra用在这题也是n^2.
这题我的理解是，做车还是从起点到终点，不换车，但通过买不同间段的票来达到最优。
如果可以往回坐，其实就完全是dijkstra的原题了，看不出考点。而这个不换车的考点
是，你要理解了dijkstra后如何写一个简版的DP算法。 |
|
s********u
发帖数: 1109 | 26 感觉准备过程中走了很多弯路，一开始看很多经验说是大多数公司cc150就够用了，是
神书，结果我做了三遍，版上很多题目只要没见过还是不会做。然后我就开始做
leetcode，目前做到一半，不会的就看看discuss版面，有一定成效。
我觉得真正提高最大的是最近看面经。感觉自己思路见识广了很多，也开始大致明白为
什么有些人一看题就知道应该用backtracking，或者dp什么的。
其实原因并不是面经这个题有什么区别，而是如果做careercup书，不会做就看答案，
答案只会告诉你这道题目怎么解，这是我觉得cc150写的不好的地方。比如他每个章节
有一点基础知识，但不会把这些跟题目对应起来。结果你还是不会分类。
做leetcode就好一点点，因为discuss上面很多人会写自己的分析过程。就是“为什么
想到这样做”。
做面经是收获最大的，因为做一道题目的时间最长，没有现成答案，不会做只能去搜资
料。虽然找资料有很多冗余的过程，但是反而开拓了见识，了解了很多分析和分类的方
法。其实就是一种“模式识别”
比如一个boggle game题，搜到网上很多人总结这个题，比如暴力回溯算法，建立trie... 阅读全帖 |
|
e********3
发帖数: 18578 | 27 BFS+DP,而且需要maintain两个距离，一个是到终点的最小距离，一个是到起点的最小
距离，计算终点的距离需要backtrack,到起点的简单比较保存最小值就行了，类似
Dijkstra算法。电面就考这个有点偏难了，尤其还是同胞就操蛋了，要是老中这么考老
印我绝对赞成。简单的实现还可以把障碍物那个的距离设成100啥的，这样自然就知道
要绕过了。
这个题目的难度比reverse linkedlist, atoi难了几个数量级。。。
我贴两个我自己写的代码抛砖引玉一下，第一个是Harry Potter最小的strength通关，
第二个是经典的Dijkstra algorithm,都是附带了测试数据自动生成的方法，你把这两
个组合一下基本就能解这道题了,过两天我有空了来写一下这道题的具体实现。
import java.util.*;
public class HarryPotter{
private static Random rand = new Random();
private static int[][] matrix;
private static ... 阅读全帖 |
|
G***Y
发帖数: 9698 | 28 《纽约生活》9月17日─9月23日
September 16, 2012 06:05 AM
【9月17日 星期一】
●束缚与被束缚：林天苗回顾展Bound Unbound: Lin Tianmiao
时间：11am-6pm
地点：亚洲协会，曼哈坦公园大道725号
查询：http://asiasociety.org/new-york/exhibitions/BoundUnbound
门票：免费。几乎每一次林天苗的个展都能带来一种华丽的精彩。这是林天苗个人事业
生涯中的首次回顾展，参展作品共29件，包括装置、雕塑等，涵盖了林天苗自1995年以
来各个阶段的代表作，其中三分之一左右借自於藏家。此外林天苗还為这次展览特别创
作新作品，在新作中，林天苗运用了骨头作為材料。
●「间谍：谍报秘密世界」Spy：The Secret World of Espionage
时间：10am-８pm
地点：曼哈坦西44街226号时报广场发现中心（Discovery Times Square Exposition）
查询：http://www.discoverytsx.com/exhibitions/spy
门... 阅读全帖 |
|
o***s
发帖数: 42149 | 29 请问：伏羲、姬昌、莱布尼茨、柏拉图，这四人当中谁是二进制思想的最早提出者？请问：以下哪个概念和公孙龙的《指物论》中的“指”字含义相近？a、变量；b、数组；c、对象；d、指针……这样的题目摆在面前，你会不会顿生“这都哪儿跟哪儿”的无助感？这就是在网上热传的让理科生沉默、让文科生流泪的一套文理综合题，题目有够让人抓狂的，不管你是文科生、理科生，不管你是工人、学生、农作物制造者还是知识分子，欢迎前来挑战，至于能做出几题就看诸君天文地理、历史哲学、数学操作等全方位的修养啦！
一，选择题(皆为单选)：
1，以下谁是二进制思想的最早提出者？
a，伏羲；b，姬昌；c，莱布尼茨；d，柏拉图。
2，以下哪个概念和公孙龙的《指物论》中的“指”字含义相近？
a，变量；b，数组；c，对象；d，指针。
3，蔺相如，司马相如；魏无忌，长孙无忌。下列哪一组对应关系与此类似？
a，PHP，Python；b，JSP，servlet；c，java，javascript；d，C，C++。
4，秦始皇吞并六国采用了以下哪种算法思想？
a，递归；b，分治；c，迭代；d，模拟。
5，雅典王子忒修斯勇闯克里特岛斩杀米诺牛的时候采用... 阅读全帖 |
|
A*********l
发帖数: 2005 | 30 1：
有DP的方法吧。
2：
直觉上感觉，是不是有DP的方法？或者是类似Dijkstra's的算法？（没仔细想，就是直觉）感觉
Dijkstra's比较像，所有到某个节点的path的weight就是这个节点的值。
3：
你的方法不对吧。
假定6个数，k=3，原来的顺序是： 1 5 3 4 2 6
heap 一开始是 1， 5， 3， 把 1 拿出来。
然后heap 是5，3， 4， 把 3 拿出来。
这排序就错了吧？3 排到2 前面去了。
要么我没看懂题或者是没看懂你原来的解法？ |
|
d*******d
发帖数: 2050 | 31 根据我的经验,一般bfs和dfs就够了,再就是top sort+relaxation就很厉害了,或者那个
三次方算法就行了.
如果你觉得你要用上dijkstra,基本上你八成已经走了弯路了,因为你要maintain一个
priority queue,现场码code半个小时内很难码干净的.
A*的话,和dijkstra没啥区别,一码事. |
|
d**********x
发帖数: 4083 | 32 恩，Dijkstra是正着贪过去，标记每点的最短路径再回溯
我要defense两点，一前面有人说了Dijkstra不好写，二复杂度是由回溯部分限制的，
除非图很稀疏。 |
|
b***e
发帖数: 1419 | 33 来自主题: JobHunting版 - 问个面试题 Dijkstra求连通算法可解。在adjacent matrix上执行Dijkstra算法，如果某一个cell
的值为1且从未被改变过，那么这个cell所对应的edge是一个canonical edge。 |
|
p********n
发帖数: 165 | 34 抛个砖：
A*算法的核心是点到点求最短距离，不是点到面。而且需要好的heuristic function，
即使是在矩阵中找点对点最短距离也不一定是最好算法。
这个题，假设gym为n^2 matrix，k个器械。 用Dijkstra计算每个器械到非障碍物的距
离，复杂度为k*n^2*log(n),其中log(n)为maintain 一个priority queue的复杂度，
queue里最多的元素不可能是n^2而是n。
然后iterate 一遍matrix，找出离k个器械距离和最小的一个element，复杂度为n^2.
所以最后复杂度为 O(k*n^2*log(n))
当然这个题两个相邻点的距离都是uniform的话，可以不用Dijkstra,而用Breath-First
Search，复杂度可以进一步降低到O(k*n^2). |
|
s**********k
发帖数: 88 | 35 第一题，能不能用Dijkstra算法？ Dijkstra算法的复杂度是 O(n^2) 或者 O(nlogn)
（用heap)。是不是我漏掉了什么。
.. |
|
l*****u
发帖数: 13 | 36 Dijkstra's algorithm in 3D Cube...
Dijkstra in 2D grid在一个点上下左右BFS，in 3D cube要做上下左右+下一层的BFS |
|
z*********n
发帖数: 1451 | 37
topological sort面试还考，但感觉现在面试连dijkstra和floyd warshall都不要求掌
握了，这也是本科教科书知识吧。上回面某家，面试官问了个带权值最短路径，我一听
虎躯一震，居然真会问dijkstra，抡起袖子就打算开搞，结果被面试官大声喝止，说你
讲讲思路，证明一下这个算法正确性就行了，不用写code，我还有点小失望呢。 |
|
r*****s
发帖数: 1815 | 38 。。。。
我面微软的时候也是
面试官问了个超简单的bfs最短路 然后问我有权怎么办
我刚要写他说算了
: topological sort面试还考，但感觉现在面试连dijkstra和floyd warshall都不
要求掌
: 握了，这也是本科教科书知识吧。上回面某家，面试官问了个带权值最短路径，
我一听
: 虎躯一震，居然真会问dijkstra，抡起袖子就打算开搞，结果被面试官大声喝止
，说你
: 讲讲思路，证明一下这个算法正确性就行了，不用写code，我还有点小失望呢。
|
|
Y*****y
发帖数: 361 | 39 恭喜啊！
不过Dijkstra这奖不是给分布计算，而不是并行计算的么？印象中这个奖是PODC发的，快10年前老板
拿过一次。
两周前还和Dijkstra的一个学生聊过天，那哥们转行去做数据库了…… |
|
t******l
发帖数: 10908 | 40 dijkstra 概念型的的 cost metric 没有线性的要求。。。具体问题可能有更巧的办法
，但 dijkstra 概念型是万金油。。。
：不是线性的
：【 在 timefall (时光崩塌) 的大作中提到: 】 |
|
u****h
发帖数: 2193 | 41 怎么修改一个图, 再跑一次dijkstra算法, 就能找出原点到其他任何一点的偶长度最短
路经..
偶长度最短路是说, 这条最短路一定要经过偶数条边.
我不知道最好算法有多好... 能跟对原图作dijkstra一样好么?
谢谢了! |
|
n****y
发帖数: 106 | 42 I want to implement some algorithm similar to dijkstra...
可是不知道怎么才能把地图网络图层生成一个dijkstra可以用的节点数据结构
If somebody needs to implement dijstra using a real map, he has to convert
the map to some data structure, right?
Any software? Any hint? Thanks a lot. |
|
m********g
发帖数: 9 | 43 During a phone interview, I was asked how to implement a BFS algorithm to
find the shortest distance path from node A to node B in a graph. I asked is
it Dijkstra, and he said no.
Isn't BFS a special case of Dijkstra when there is no weight?
Strange. |
|
r***r
发帖数: 153 | 44 结果一样，但是Dijkstra成本高很多阿
BFS is O(|E|+|V|)
Dijkstra 有很多的priority queue操作，
如果用简单的堆实现，需要 O(|V|^2)
用复杂的Fibonacci heap，（可以得到最优complexity，但没有很多实际意义）也是 O
( |E| + |V| log |V| )
is |
|
I*******e
发帖数: 1879 | 45 ☆─────────────────────────────────────☆
CHKRUN (小鸡快跑) 于 (Fri May 8 14:57:34 2009) 提到:
Google map是怎么算最短路径的？
假如有一个非常非常大的network,nodes有250,000,edge有500,000
现在用的是Dijkstra with heap implementation,如果两点离的太远的话，非常慢，我
正考虑用A* 和 Dijkstra with Fibonacci heap，但是估计了下，应该还是不够快。
不知道有没有什么比较practical的shortest path algorithm？google map,Garmin,和
其他网上map是用的什么算法呢？多谢。
☆─────────────────────────────────────☆
smugmug (时刻拥有春天般的美丽心情) 于 (Fri May 8 15:13:21 2009) 提到:
Critical Graph (only containts major vertices) |
|
g*********s
发帖数: 1782 | 46 "变化"怎么定义？一次只能改动一个字母？能增/删吗？
如果是一次只能改一个，那bfs够了。
bfs可看作dijkstra的特例，dijkstra又可看成A*的特例。
transformed |
|
r***s
发帖数: 737 | 47 今天真是见到大大牛的了。您老人家不拿图灵奖
简直就是没天理了。
敢问您对于在lamport之前提出并行同步机制的人
如Dijkstra算法怎么看， 对于lamport在dijkstra
的一系列算法基础上给出的理论证明有什么改进
意见？ lamport开创的用Induction invariant
证明算法正确性的方法同时期还有谁在研究?
他们提出的方法各有什么优劣？
请问在时序逻辑里fairness 的概念是什么意思？
Strong fairness weak fairness 最大的区别是什么，
这些区别在证明safety conditions 和
Liveness conditions 的重要性在哪里.
另外现在时髦的Raft 和 Zookeeper Replication Protocol
和Paxos 区别是什么？ |
|
x*****u
发帖数: 3419 | 48 http://www.fortran.com/come_from.html
We don't know where to GOTO if we don't know where we've COME FROM. This
linguistic innovation lives up to all expectations.
By R. Lawrence Clark*
From DATAMATION, December, 1973
Nearly six years after publication of Dijkstra's now-famous letter, [1] the
subject of GOTO-less programming still stirs considerable controversy.
Dijkstra and his supporters claim that the GOTO statement leads to
difficulty in debugging, modifying, understanding and proving program |
|
|
c***s
发帖数: 70028 | 50 2006年，会议五十年后，当事人重聚达特茅斯。左起：摩尔，麦卡锡，明斯基，赛弗里奇，所罗门诺夫
背景
现在一说起人工智能的起源，公认是1956年的达特茅斯会议。殊不知还有个前戏：1955年，美国西部计算机联合大会（Western Joint Computer Conference）在洛杉矶召开，会中还套了个小会：“学习机讨论会”（Session on Learning Machine）。讨论会的参加者中有两个人参加了第二年的达特茅斯会议，他们是塞弗里奇（Oliver Selfridge）和纽厄尔（Allen Newell），塞弗里奇发表了一篇模式识别的文章，而纽厄尔则探讨了计算机下棋，他们分别代表两派观点。讨论会的主持人是神经网络的鼻祖之一皮茨（Pitts），他最后总结时说：“（一派人）企图模拟神经系统，而纽厄尔则企图模拟心智（mind）……但殊途同归。”皮茨眼可真毒，这预示了人工智能随后几十年关于“结构与功能”两个阶级、两条路线的斗争。
开聊达特茅斯会议之前，先说六个最相关的人。首先，会议的召集者麦卡锡（John McCarthy）当时是达特茅斯学院的数学系助理教授。两年前（1954... 阅读全帖 |
|
