Solving the shortest path problem

[cgtalk]

hi
can any body help me in how can i use threads or multithreading to solve the shortest path problem
i need a code or links to codes please

[D_Drmmr]

Please give some more specifications.
- What do you want to know? Shortest path between 2 nodes, from one node to all other nodes or between all pairs of nodes.
- What kind of algorithm are you using?
- How do you want to use multithreading in that algorithm?

Multithreading does not solve the shortest path problem, shortest path algorithms do. Please be more specific.

[cgtalk]

thanks for replying
the story is that i'm studying a course about parallel processing and one of
our lessons is about Dynamic programming , one of the topics is about the shortest path problem " Serial monadic DP" the reference book is "introduction to paralle computing analysis and algorithm design" i think that's the name couse i couldn't find it free
so as a course project i have to study ch#9 " Dynamic programming" and then to make a presentation to the student about it , also there are 50 degree for implementing a program that will use thread or multithreading
in solving the shortest path problem between one node in a level and all the other nodes in the next levels " we didn't study any thing about threads or multithreading in the colouge so that's why i didn't know how to use them in programming
there are a matrix usage and recalculating of results of the nodes
The connection is between any node in a level and all the other nodes in the next level
i hope you understand me

[mehdi62b]

you should consider Folyd Warshal (http://en.wikipedia.org/wiki/Floyd-Warshall_algorithm) algorithm for dynamic programming,
this is its pesudo codeFunction Floyd(L[1..n,1..n]):array[1..n,1...n])
array D[1..n,1..n]
D = l
for k = 1 to n do
for i = 1 to n do
for j = 1 to n do
D[i,j] = Min(D[i,j] ,D[i,k]+D[k,j])
return Dfor speeding up its executing time you should make some threads for i and j while you are computing the minimum value for array items..as far as I think you just can work on the two most inner loops(I mean i and j)for example in every k step compute all the n^2 array items concurrently by making n^2 threads.(i.e if n=1000 you should make 1,000,000 threads,is this possible? :ehh: )