Solved

k-shortest path implementation with C language

Posted on 2008-10-04
4
572 Views
Last Modified: 2012-05-05
Hi.
By using Dijkskta algorimth i have implemented an application for find the 1st shortest path of an optical network. Unfortunately, this is not enough. It is necessary to calculate the 2st & 3rd shortest path, using the same algorithm or something else, always by using language C. Do you have any idea how to do it??

www.cs.bham.ac.uk/~mhe/foundations2/node113.html - 16k -
(my code is similar to  the code of the above link)
0
Comment
Question by:tsakyr
  • 3
4 Comments
 
LVL 45

Expert Comment

by:sunnycoder
ID: 22640091
http://www.dis.uniroma1.it/~challenge9/papers/santos.pdf

Implementation of K-shortest Path Dijkstra Algorithm used in All-optical Data Communication Networks
http://www.u.arizona.edu/~saurabh/SIE/kDijkstra546.pdf
0
 
LVL 45

Accepted Solution

by:
sunnycoder earned 500 total points
ID: 22640100
Btw, you can use your existing algo too ...

Find the shortest path
second_shortest = HIGH_VALUE
for all edges in shortest path
     remove the edge
     current = find the shortest path
     second_shortest = min (second_shortest, current)
     put back edge
end for

If you iterate over this pseudocode k times - removing the edge for shortest path each time, you would have k shortest paths.
0
 

Author Closing Comment

by:tsakyr
ID: 31503003
Realy, thanks a lot.
0
 
LVL 45

Expert Comment

by:sunnycoder
ID: 22640216
Glad to help :)

Was wondering why you chose a B grade. Pls refer to grading guidelines here
http://www.experts-exchange.com/help.jsp#hi403
0

Featured Post

Free Tool: Path Explorer

An intuitive utility to help find the CSS path to UI elements on a webpage. These paths are used frequently in a variety of front-end development and QA automation tasks.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use for-loops in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.

828 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question