finding shortest path...

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.

.

Relevant Pages

  • Re: Problem on an nxn grid
    ... "See Spot Run" in the vocabulary of Graph Theory. ... Gibbons's "Algorithmic Graph Theory" gives a pseudo-code ... parts of the Edmonds algorithm (such as the Hungarian ... All weights are assumed to be ...
    (sci.math)
  • RE: [REPORT] cfs-v4 vs sd-0.44
    ... The definition for proportional fairness assumes that each thread has a ... threads have fixed weights throughout the interval. ... approximate this ideal scheduler (often referred to as Generalized ... The goal of a proportional-share scheduling algorithm is to minimize the ...
    (Linux-Kernel)
  • Re: Compressing your levels
    ... the algorithm (with a modified function ... One should probably count the weights ... you run seam removal to remove excess portions ... another portion of the dungeon is removed? ...
    (rec.games.roguelike.development)
  • Re: how to compare between different training algorithms, to find the best algorithm???
    ... you just looking for the best algorithm to use with your ... to searching over a lot of different parameters and initial weights. ... & test set. ... answers for every trial because of random weights and biases. ...
    (comp.soft-sys.matlab)
Loading