Need Help - Shortest Path Problem

mas287 · #1 16-Jun-2008, 20:51

Hi,

I have implemented Dijkstra's algorithm before and now I have a project to implement another algorithm to solve the Shortest Path problem. This algorithm is known as Dantzig's algorithm.

I have developed Directed Ascyclic Graph(DAG) and would like to use this algorithm to get the shortest path.

Dantzig's algorithm:

for s=1 to n do Single_Source(s)

prosedure Single_Source(s)
S={s} ;
d[s]=0;

initialize the set of candidates to {(s,t) }, where (s,t) is the shortest edge from s
Dantzig_expand_S(n)

end {Single_Source}

prosedure Dantzig_expand_S(limit)

while|s| < limit do begin
let (c, t) be the candidate of least weight, where the weight of (c,t) is given by d[c] + c(c,t);

S = S + {t};
d[t] = d[c] + c(c,t);

if |s| = limit then break;
add to the set of candidates the shortest useful edge from t;

for each useless candidate (v,t) do

replace (v,t) in the set of candidates by the next shortest useful edge from v

end for

end while
end {Dantzig_expand_S }

end for

My Question :

I am confuse about to build the set of candidates. If anyone can help, I really appreaciate it.

ocicat · #2 16-Jun-2008, 23:07

Quote:

Originally Posted by mas287

I am confuse about to build the set of candidates.

Look at the information already presented on your algorithm. You need some means of identifying edges which probably consists of weighted edge & end-point information. Make a structure with fields which contains this relevant information.

As for how to construct a "set", the simplest solution would be to create an array large enough to handle all the edge structures discussed above. If this is code which will only be used once or only a few times, this may be sufficient. If you expect to use it again & again, you may want something more sophisticated as in creating a linked list of these structures, however, this also depends upon your knowledge of C & whether you have time to debug all the details.

You may also want to sort this array/linked list once populated given that it appears you want to continually pull off the shortest path on each iteration.

mas287 · #3 16-Jun-2008, 23:46

Thank you ocicat.

I've declared all the vertices together with their edges. I generated them using rand( ) .

For Example:
OUT(0) = {(0,2),(0,3),(0,4)} with cost {d[0,2] = 4 ,d[0,3] = 3, d[0,4] = 1}

CPP / C++ / C Code:

struct g_edge{
  int vertex_number;
  int destination;
  struct g_edge *next;
};
 
struct g_vertex {
  struct g_edge *edge1;
  struct g_edge *end_edge;
}; 

j=0;
edge_ptr = vertices[0].edge1;   /* starting */
    while(edge_ptr) {
        w = edge_ptr->vertex_number;
        d[w] = edge_ptr->destination;
        front[j] = w;
         j++;
         edge_ptr = edge_ptr->next;
    }


/* from the above code, we can get list of vertices from vertex[0] 
 * or OUT(0) with their edge values.
 */

If I want to sort all the OUT(0) vertices, should I use Array or linked list ? How to sort them ?

ocicat · #4 17-Jun-2008, 00:12

Quote:

Originally Posted by mas287

If I want to sort all the OUT(0) vertices, should I use Array or linked list ? How to sort them ?

The benefits/restrictions include:

With an array, you can only store up to the size of the array; no more. However with an array, implementing sorting is simpler.
With implementing a linked list, you are only limited by how much process space is allocated to your application. This solution is more flexible, however, the coding is more sophisticated & you will need to implement sorting (manipulating all pointers...) yourself.
Implementing an array-based solution is probably faster.

As to your question about how to sort, this depends upon how much data you have, & how fast you want execution. I'm guessing that your data set isn't too large nor do you care that execution with one algorithm runs one nanosecond faster than another. I suspect the simplest solution would be to do an insertion sort. Traverse the array or list until you find the first value higher than the value being inserted. Shift all array contents to make space for the new entry, or create a new node & adjust the pointers of the previous & next node appropriately.

mas287 · #5 17-Jun-2008, 22:06

Thanks again ocicat. I appreciate it so much.

I have sorted vertices from the first vertex ( OUT(StartVertex) ) using a simple array as you suggested. My coding is just like this:

CPP / C++ / C Code:

 j = 0;

    
    edge_ptr = vertices[StartVertex].edge1;
    
    while(edge_ptr) {
        w = edge_ptr->vertex_no;
        d[w] = edge_ptr->dist;
        front[j] = w;
        j++;
        
        edge_ptr = edge_ptr->next;
        }
    
       for(q = 0; q < j; q++)   /*here I try to sort */
        {
           if(d[front[q+1]])
            {
            if(d[front[q]] > d[front[q+1]]) 
                  {
                           temp = front[q];
                           front[q]=front[q+1];
                           front[q+1] = temp;
                  }
            }               
        }

Is that what you have suggested ?

ocicat · #6 18-Jun-2008, 03:59

Quote:

Originally Posted by mas287

Is that what you have suggested ?

It appears that you are keeping a parallel array to simplify sorting. This is one way to solve the problem, & if it works for you, you are the best judge for knowing how to maintain your own code.

Depending upon your interest, skill, curiosity, you might look at using qsort() to accomplish the array sorting for you, but this simply takes advantage of the standard generic implementation of Quicksort over having to code it yourself. Only with huge data sets would this provide any significant improvement over simpler sorting algorithms like insertion sort or Bubblesort, but it relieves you of the responsibility of re-inventing sorting code yourself.
You may also want to consider inserting edges into your linked list in sorted order which will get rid of all duplicated effort.

Writing code professionally requires balancing how useful is the code being written, anticipating its lifetime, honestly knowing one's ability, & using what time is allotted effectively. Realistically, these are the factors which influence what is considered "good".

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Shortest Path Program.	bomber456	C++ Forum	1	05-Mar-2007 13:32
shortest path algorithm and file saving	Pandiani	C++ Forum	10	17-Jul-2006 11:46
Graphic problem in Unreal Tournament 2004	zerox	Computer Software Forum - Games	10	09-Oct-2005 13:31
a significant problem after installing Xp	mohammad	Computer Software Forum - Windows	10	09-Aug-2005 08:03
PATH points to nonexistent dir	wavez	C Programming Language	5	06-Oct-2004 04:04

Need Help - Shortest Path Problem

Re: Need Help - Shortest Path Problem

Re: Need Help - Shortest Path Problem

Re: Need Help - Shortest Path Problem

Re: Need Help - Shortest Path Problem

Re: Need Help - Shortest Path Problem