g****p
发帖数: 94 | 1 Let G = (V, E) be a weighted, directed graph with weight function w : E → {
1, 2, ..., W } for some positive integer W , and assume that no two vertices
have the same shortest-path weights from source vertex s. Now suppose that
we define an unweighted, directed graph G' = (V ∪ V', E') by replacing each
edge (u, v) ∈ E with w(u, v) unit-weight edges in series.
Questions：
1. How many vertices does G' have?
2. Now suppose that we run a breadth-first search on G'. Show that the order
in which vertic | s***e
发帖数: 284 | 2 *-----2------*
u v
转换成
*------------*------------*
u u1 v
权重是多少，G'就变成多少条边
{
vertices
that
each
order
'
p
【在 g****p 的大作中提到】
: Let G = (V, E) be a weighted, directed graph with weight function w : E → {
: 1, 2, ..., W } for some positive integer W , and assume that no two vertices
: have the same shortest-path weights from source vertex s. Now suppose that
: we define an unweighted, directed graph G' = (V ∪ V', E') by replacing each
: edge (u, v) ∈ E with w(u, v) unit-weight edges in series.
: Questions：
: 1. How many vertices does G' have?
: 2. Now suppose that we run a breadth-first search on G'. Show that the order
: in which vertic
| g*********e
发帖数: 42 | 3 这个weight function是怎么定义的，如果不是 one to one的，
第一题怎么解呀 |
|
