Re: Shortest Path
- From: "GCRhoads" <rhoads@xxxxxxxxxxxxxxx>
- Date: 27 Feb 2007 11:24:52 -0800
On Feb 27, 12:02 pm, "Ez_Alg" <virtualreal...@xxxxxxxxx> wrote:
Hi Everyone,
Can you guide me through the following problem:
in the shortest path problem if we have vertex costs in addition to
edge lengths how is the algorithm changed! I am trying to modify the
Dijkstra and Bellman_ford algorithm to answer this but i am stuck!!!
any Hints
I assume that the path weight is the sum of the edge weights plus the
sum of the vertex weights.
You can solve this by running a standard shortest path algorithm
on the following modified graph. Split each vertex V with weight W
into two vertices V1 and V2, and add a directed edge V1 ---> V2
of weight W.
Case 1: Your initial graph is directed.
For each directed edge U ---> V of weight W in your initial graph,
have a directed edge U2 ---> V1 of weight W in your new graph.
Case 2: Your initial graph is undirected.
For each edge U --- V of weight W, have directed edges U2 ---> V1
and V2 ---> U1 both of weight W.
Now to find the shortest path from X to Y in your initial graph,
find the shortest path from X1 to Y2 in your modified graph.
If you don't want to include the weight of the initial vertex in your
total path weight, then start from vertex X2 instead.
-- Glenn C. Rhoads
.
- References:
- Shortest Path
- From: Ez_Alg
- Shortest Path
- Prev by Date: Shortest Path
- Next by Date: Re: Shortest Path
- Previous by thread: Shortest Path
- Next by thread: Re: Shortest Path
- Index(es):
Relevant Pages
|
