By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
443,918 Members | 1,923 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 443,918 IT Pros & Developers. It's quick & easy.

c++ code for shortest path in the graph

P: n/a
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.

Mar 26 '06 #1
Share this Question
Share on Google+
4 Replies


P: n/a
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:
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.


Haha! Somebody's going to fail comp science...
Mar 26 '06 #2

P: n/a
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

P: n/a
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

P: n/a
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 discussion thread is closed

Replies have been disabled for this discussion.