d********t
发帖数: 9628 | 1 假设是direct，每条路weight都是1，哪里大侠能介绍一下算法吗？ |
f*******t
发帖数: 7549 | |
d********t
发帖数: 9628 | 3
wiki是没写怎么找single-source-single-destination啊？而且也没看到BFS
【在 f*******t 的大作中提到】
: BFS，看wikipedia
|
S**I
发帖数: 15689 | 4 Dijkstra's Algorithm
【在 d********t 的大作中提到】
: 假设是direct，每条路weight都是1，哪里大侠能介绍一下算法吗？
|
d********t
发帖数: 9628 | 5
thanks.
【在 S**I 的大作中提到】
: Dijkstra's Algorithm
|
f*******t
发帖数: 7549 | 6 不过这个东西不是基本算法么。。
简单的说就是从source开始，每个循环把当前所有连接的其它node找出来，不断扩张搜
索范围，直到遇见destination。访问过的node要通过某种方式标记为visited，防止重
复。
【在 d********t 的大作中提到】
:
: thanks.
|
d********t
发帖数: 9628 | 7 我不能一眼看出BFS和DFS找的结果是否一样啊
【在 f*******t 的大作中提到】
: 不过这个东西不是基本算法么。。
: 简单的说就是从source开始，每个循环把当前所有连接的其它node找出来，不断扩张搜
: 索范围，直到遇见destination。访问过的node要通过某种方式标记为visited，防止重
: 复。
|
a*****n
发帖数: 158 | 8 直接用BFS吧，用DIJKSTRA有点浪费。。。 |
q****x
发帖数: 7404 | 9 bfs是dijkstra特例，此时优先队列退化成普通队列。
【在 a*****n 的大作中提到】
: 直接用BFS吧，用DIJKSTRA有点浪费。。。
|
n*******w
发帖数: 687 | 10 嗯，Dijkstra肯定得掌握。虽然每个edge权重是1，还是得用优先队列吧。
还有个Bellman-Ford也可以考虑。
【在 q****x 的大作中提到】
: bfs是dijkstra特例，此时优先队列退化成普通队列。
|
a********m
发帖数: 15480 | 11 恩。权重是1的话dij也就是bfs了，省了排序部分。另外如果有预测信息可以用a*.
【在 q****x 的大作中提到】
: bfs是dijkstra特例，此时优先队列退化成普通队列。
|
