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.
4  12085 
On 25 Mar 2006 16:54:09 -0800, "Shuch" <Sh**********@g mail.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??????m y 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...
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..that s y i m askin if someone has some code....
On 26 Mar 2006 02:46:21 -0800, "Shuch" <Sh**********@g mail.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..tha ts 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. This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics | |
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 seems like a lot of work and I am sure that
it has been done many times before.
From (x,y) coordinates I need to place the user in a zone and find the
shortest path to all other zones.
Any suggestions are more than welcome. I would hate to reinvent...
|
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 parse then it takes about
O(N^2) where N is the # of vertices, too much for large graphs.
Furthermore, I don't need to know the all the path from a start point to
every other single vertex as Dijkstra would provide. Just the shortest
path from a...
|
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. The others are free to go over ...
(I already found that part)
-> http://users.pandora.be/hebbrecht/jochen/c++/test.cpp
|
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 extension an efficient
algorithm to compute this.
Any help much appreciated,
Adam
|
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 since there
is a possibility to exist more than one shortest paths with the same
distance.
Does anyone has any idea how this could be done?
Code
| | |
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,
|
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 package for my Python 2.4 under
windows. Can someone please provide me instructions for installing
libboost for python?
In alternative, if someone can point out to a fast Dijkstra shortest
path in python (the network is over 1 million vertexes), I...
|
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):
def __init__(self):
self.G = defaultdict(dict)
self.E = defaultdict(dict)
|
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 simple function to determine a path between two nodes.
It takes a graph and the start and end nodes as arguments. It will
return a list of nodes (including the start and end nodes) comprising
the path. When no path can be found, it returns None....
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look !
Part I. Meaning of...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed.
This is as boiled down as I can make it.
Here is my compilation command:
g++-12 -std=c++20 -Wnarrowing bit_field.cpp
Here is the code in...
| | |
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
|
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own....
Now, this would greatly impact the work of software developers. The idea...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 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 a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules.
He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms.
Adolph will...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one.
At the time of converting from word file to html my equations which are in the word document file was convert into image.
Globals.ThisAddIn.Application.ActiveDocument.Select();...
|
by: TSSRALBI |
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs.
The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols.
I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
|
by: muto222 |
last post by:
How can i add a mobile payment intergratation into php mysql website.
| | |
by: bsmnconsultancy |
last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...
| |
