472,961 Members | 1,500 Online

# c++ code for shortest path in the graph

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.

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.

-------------------------------------

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....
regards.

Mar 26 '06 #1
4 12048
On 25 Mar 2006 16:54:09 -0800, "Shuch" <Sh**********@gmail.com> wrote:
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:
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....
regards.

Haha! Somebody's going to fail comp science...
Mar 26 '06 #2
haha...thats not possible...:)...coz i have some ideas but the problem
is just that i m not able to figure it out how to write it
correctly..thats y i m askin if someone has some code....

Mar 26 '06 #3
On 26 Mar 2006 02:46:21 -0800, "Shuch" <Sh**********@gmail.com> wrote:
haha...thats not possible...:)...coz i have some ideas but the problem
is just that i m not able to figure it out how to write it
correctly..thats y i m askin if someone has some code....

Wrong group, though. Find a specific algorithms group or web forum.
This group is for the C++ language itself.

Also, head down to the library.
Mar 26 '06 #4
On 25 Mar 2006 16:54:09 -0800, "Shuch" <Sh**********@gmail.com> wrote
in comp.lang.c++:
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:

Send us your instructor's email address and we'll save you even more
time by turning in the homework as well.
--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://c-faq.com/
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.learn.c-c++
http://www.contrib.andrew.cmu.edu/~a...FAQ-acllc.html
Mar 27 '06 #5

This thread has been closed and replies have been disabled. Please start a new discussion.