Hi,
I am trying to solve a problem, I think it has to do with Dijkstra's
algorithm ( shortest path problem ) which is :
1 function Dijkstra(G, w, s)
2 for each vertex v in V[G] //
Initializations
3 d[v] := infinity // Known
distance function from s to v
4 previous[v] := undefined
5 d[s] := 0 // Distance
from s to s
6 S := empty set // Set of all
visited vertices
7 Q := V[G] // Set of all
unvisited vertices
8 while Q is not an empty set // The
algorithm itself
9 u := Extract_Min(Q) // Remove best
vertex from priority queue
10 S := S union {u} // Mark it
'visited'
11 for each edge (u,v) outgoing from u
12 if d[u] + w(u,v) < d[v] // Relax (u,v)
13 d[v] := d[u] + w(u,v)
14 previous[v] := u
here is my question:
In Internet routing, there are delays on lines but also, more
significantly, delays at routers.
Suppose that in addition to having edge lengths l(e) : e in E, a graph
also has vertex costs
{c(v) : v in V. Now define the cost of a path to be the sum of its
edge lengths, plus the costs of
all vertices on the path (including the endpoints).
Here is what we want:
Input: A directed graph G = (V,E); positive edge lengths l(e) and
positive vertex costs c(v) ; a starting vertex s in V.
Output: An array cost[.] such that for every vertex u, cost[u] is the
least cost of any
path from s to u (i.e., the cost of the cheapest path), under the
definition above.
Notice that cost[s] = c(s)
Any Help would be appriciated
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
