Need advice on shortest path algorithms

[Blondeamon]

Hello guys

under a project i have to complete for this semester i have to think and implement a shortest path algorithm other than the ones i have already coded so far for this course , which are:

- Bellman Ford
- Floyd
- Kruskal

The whole project is a bit weird because it says that i have to : make a "new" algorithm that computes the shortest path on a directed graph with positive weights on vertices and edges ,given in a txt file with this content (the graph i mean is this):

[15]
0 4 0 0 0 0 4 0 0 0 0 0 0 0 0
0 0 5 0 0 0 2 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 5 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 6 0 0 0 0 0
3 0 0 0 0 0 0 0 0 0 2 0 0 0 0
0 0 0 0 0 1 0 0 0 0 5 7 0 0 0
0 0 3 0 0 0 0 0 7 0 0 0 0 9 0
0 0 0 0 0 0 0 0 0 0 0 0 0 8 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 4
0 0 0 0 0 0 0 0 0 0 0 6 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 4 0 0
0 0 0 0 0 0 0 2 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 5
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

and the graph itself is this:

http://img152.imageshack.us/img152/1185/65843748il0.jpg

I can use any of the algorithms i already coded or a new one o can think of , as long as this time i also add not only the weights of the edges but the weight of each vertice as well.
The weights of the edges are these ones:

[15]
1 4 2 2 3 4 4 5 2 3 1 1 1 1 2

So now i have been thinking....what should i use to design a new shortest path algorithm that also counts the weights of the vertices and is based on some other already known shortest path algorithms ? (i hate re-inventing the wheel, i mean coding from scratch stuff already out there).

Just need some theoretical advice on this....would be grateful if you could share some ideas. Maybe also BFS or DFS could be used or A* ...dont know. Im open to suggestions.

Thanks in advance for your answers

[Blondeamon]

Any ideas ?

[Prathvi]

Hi
Why can't you try Dijkstra's algorithm?

[Blondeamon]

I have already coded Dijkstra's algorithm for this course.

What it asks for us now is to think of a new algorithm that calculates shortest paths but this time it includes the weights of the vertices too not only the weights of the edges.

Should i just take Dijkstra or Kruskal that i have already coded and add the vertice weights into the game ?

[vijayan121]

> Should i just take Dijkstra or Kruskal that i have already coded and add the vertice weights into the game ?

that would not work. Kruskal does something like this
create a set containing all the edges in the graph
... remove an edge with minimum weight from the set
etc.

if you also need vertice weights to be taken into consideration, directly using Kruskal (with the vertice weights added) would add the weight of each intermediate vertex in the path twice. the algorithm has to be modified to correct for this.

[Blondeamon]

Then maybe should i use the Bellman Ford instead ?

This is the whole Bellman Ford function i created for earlier projects.

http://phpfi.com/315376

The part that calculates and does the job is this one but it only take into consideration edge weights....so i guess i must modify this somehow to add vertice weights. Am i correct ?

for (i = 0; i < N - 1; ++i)  
  {		
         for (j = 0; j < M; ++j) 
		 { //checking neighbohours about minimum cost to jump to
             if (label[E[j].u] > label[E[j].v] + E[j].weight  )  
             {
                label[E[j].u] =   E[j].weight + label[E[j].v];
				parent[E[j].u]=E[j].v;  //setting parents if accepted
			 }
		}
  }

N is the number of vertices , M is the size of the label array.

[vijayan121]

> so i guess i must modify this somehow to add vertice weights. Am i correct ?

yes, i think that should work.
you must be aware that Bellman-Ford does not scale well to large graphs and can result in infinite loops on an ill-formed graph (with unreachable nodes).
so you may want to do a sanity check first.

[Blondeamon]

Perfect , i'll start right away and post my progress when done.

Thanks for the help mate

[Blondeamon]

And here it is:

void BellmanFord(Edge E[], int N, long M, int start, int end)
{
     int i = 0, j = 0;
     
     /*                Memory Allocations               */
     if ((l=(int *)malloc(N*sizeof(int))) == NULL)
     {
                 fprintf(stderr, "Out of memory!\n");
                 exit(1);
     }
     if((p=(int *)malloc(N*sizeof(int))) == NULL)
     {
                fprintf(stderr, "Out of memory!\n");
                exit(1);
     }
     /*             End of Memory Allocations            */
     
     
    
     for(i = 0 ; i < N ; i++)
     {
           l[i] = 10000000; 
           p[i] = NILL; 
     }// end for
     
     l[start] = E[start].vertex_weight;
                                       E[start].vertex_weight
     
     for(i = start; i < N-1; i++)//Bellman Ford
     {
           for (j = 0; j < M; j++)
           {
               if (l[E[j].u] > l[E[j].v] + E[j].weight)//found better path
               {
                 //set label
                 l[E[j].u] = l[E[j].v] + E[j].weight + E[E[j].u].vertex_weight;
                 //set parent
                 p[E[j].u] = E[j].v;
                 
               }//end if
           }//end for
     }//end for
     
     if (l[end] == 10000000)
     {
                printf("\n\nCannot reach target node!!!\n\n");
                return 0;
     }
     else
     {
                printf("\nThe path's weight is... %d", l[end]);
     }
   
     printf("\nThe path is...");
     
     int temp_vertex = end;
     while(p[temp_vertex] != start)
     {
                      printf("(%d, %d) ",p[temp_vertex], temp_vertex);
                      temp_vertex = p[temp_vertex];	 
     }
     printf("(%d, %d) ",p[temp_vertex], temp_vertex);
     printf("\n");
     
     //freeing memory
     free(l);
     free(p);
     
     return 0;
}

Just in case someone needs it