S
Shuch
Hi all,
I am in shortage of time...and i want to know if someone has a code
written in c++ or c for finding the shortest path using stack or
queue??????my specifications r as follow:
Input data:
n = integer number representing the number of vertices
k = small integer number representing the maximal vertex degree
G = unoriented labeled connected graph G with n vertices and maximal
degree k
u,v = a pair of vertices of graph G
s = integer number
p = number of processors ----for the time being its not necessary...
Recommendation for generating G:
Use graph generator Generator1 with type -t 1. It generates unoriented
connected graph. Then the edges must be labeled by random weights from
interval <-255,255>. Make sure that some edges have negative weights,
since if edges have only positives weights, the problem has polynomial
complexity and it is easy to solve.
Task:
Find a path (each vertex must be visited at most once) connecting pair
of vertices u a v such that the sum of edge labels is maximal over all
possible such paths and at the same time, lower than s.
Output of the algorithm:
Information whether such a path exists. If so, then the sequence of
edges of the minimal path with the weights of its edges.
Sequential algorithm:
The sequential algorithm is of type BB-DFS with the search depth
bounded by |V|-1. A possible final state is a path connecting vertices
u and v. The price to be minimized is the total weight of the path. The
lower bound on the path weight is c-1. The algorithm terminates if the
price is equal to the lower bound. Otherwise, the algorithm must
perform exhaustive search. Note that a solution may not exist.
-------------------------------------
PLEASE PLEASE PLEASE PLEASE...its a very humble request if anyone has
any idea regarding this then PLEASE MAIL a copy of it on my mail id as
well....i will b waiting for atleast SOME HELP....
please help me outt
(
regards.
I am in shortage of time...and i want to know if someone has a code
written in c++ or c for finding the shortest path using stack or
queue??????my specifications r as follow:
Input data:
n = integer number representing the number of vertices
k = small integer number representing the maximal vertex degree
G = unoriented labeled connected graph G with n vertices and maximal
degree k
u,v = a pair of vertices of graph G
s = integer number
p = number of processors ----for the time being its not necessary...
Recommendation for generating G:
Use graph generator Generator1 with type -t 1. It generates unoriented
connected graph. Then the edges must be labeled by random weights from
interval <-255,255>. Make sure that some edges have negative weights,
since if edges have only positives weights, the problem has polynomial
complexity and it is easy to solve.
Task:
Find a path (each vertex must be visited at most once) connecting pair
of vertices u a v such that the sum of edge labels is maximal over all
possible such paths and at the same time, lower than s.
Output of the algorithm:
Information whether such a path exists. If so, then the sequence of
edges of the minimal path with the weights of its edges.
Sequential algorithm:
The sequential algorithm is of type BB-DFS with the search depth
bounded by |V|-1. A possible final state is a path connecting vertices
u and v. The price to be minimized is the total weight of the path. The
lower bound on the path weight is c-1. The algorithm terminates if the
price is equal to the lower bound. Otherwise, the algorithm must
perform exhaustive search. Note that a solution may not exist.
-------------------------------------
PLEASE PLEASE PLEASE PLEASE...its a very humble request if anyone has
any idea regarding this then PLEASE MAIL a copy of it on my mail id as
well....i will b waiting for atleast SOME HELP....
please help me outt
(regards.