473,324 Members | 2,178 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,324 software developers and data experts.

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.

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
4 12074
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
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.

Similar topics

6
by: Lau | last post by:
How do I easily calculate the shortest path between two geographical spots on a map? The map is divided into zones. So I guess it is possible to use Dijkstra’s Shortest Path algorithm, but it...
6
by: ThanhVu Nguyen | last post by:
Hi all, I need recommendation for a very fast shortest path algorithm. The edges are all directed, positive weights. Dijkstra shortest path will solve it just fine but the if the graph is not...
20
by: Webdad | last post by:
Hi! I running my first year as industrial engineer (informatics) We have an assignment to do : .... create a playfield (matrix). Some places in that field are blocked, so you can't pass them....
1
by: Adam Hartshorne | last post by:
Hi All, I know how to calculate the all-pair shortest paths matrix on an undirected graph. I was wondering how I could extend this to calculate the all-pair average path, or if not a simple...
5
by: costantinos | last post by:
Hello. I have implemented the Dijkstra shortest path algorithm, it works fine but I have one question on how I can improve something. I want to find all the possible shortest paths from a node...
0
by: diffuser78 | last post by:
Is there any function in networkx which can compute the shortest mean path length. (Shortest length between all pairs of the nodes in the graph). Thanks,
2
by: Bytter | last post by:
Hi everyone, I need to implement a very quick (performance-wise) Dijkstra shortest path in python, and found that libboost already has such thing. Problem is: I cannot find the installation...
0
by: Hugo Ferreira | last post by:
While trying to optimize this: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/119466 .... and still have a fast edge lookup, I've done the following tweaks: class PathFind(object):...
9
by: reachmsn | last post by:
Hi, At the url http://www.python.org/doc/essays/graphs.html there is some code by Guido Van Rossum for computing paths through a graph - I have pasted it below for reference - Let's write a...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.