C++ RSS C++ RSS

Need advice on shortest path algorithms

Please support our C++ advertiser: Intel Parallel Studio Home
Reply

•
•
Join Date: Dec 2007
Posts: 21
Reputation: Blondeamon is an unknown quantity at this point 
Solved Threads: 0
Blondeamon's Avatar
Blondeamon Blondeamon is offline Offline
Newbie Poster

Need advice on shortest path algorithms

 
0
  #1
May 5th, 2008
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):

C++ Syntax (Toggle Plain Text) 
  1. [15]
  2. 0 4 0 0 0 0 4 0 0 0 0 0 0 0 0
  3. 0 0 5 0 0 0 2 0 0 0 0 0 0 0 0
  4. 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0
  5. 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0
  6. 0 0 0 0 0 0 0 0 1 6 0 0 0 0 0
  7. 3 0 0 0 0 0 0 0 0 0 2 0 0 0 0
  8. 0 0 0 0 0 1 0 0 0 0 5 7 0 0 0
  9. 0 0 3 0 0 0 0 0 7 0 0 0 0 9 0
  10. 0 0 0 0 0 0 0 0 0 0 0 0 0 8 0
  11. 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4
  12. 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0
  13. 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0
  14. 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0
  15. 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5
  16. 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:

C++ Syntax (Toggle Plain Text) 
  1. [15]
  2. 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
Last edited by Blondeamon; May 5th, 2008 at 7:28 pm.
Reply With Quote Quick reply to this message  
•
•
Join Date: Dec 2007
Posts: 21
Reputation: Blondeamon is an unknown quantity at this point 
Solved Threads: 0
Blondeamon's Avatar
Blondeamon Blondeamon is offline Offline
Newbie Poster

Re: Need advice on shortest path algorithms

 
0
  #2
May 7th, 2008
Any ideas ?
Reply With Quote Quick reply to this message  
•
•
Join Date: Aug 2007
Posts: 17
Reputation: Prathvi is an unknown quantity at this point 
Solved Threads: 0
Prathvi Prathvi is offline Offline
Newbie Poster

Re: Need advice on shortest path algorithms

 
0
  #3
May 7th, 2008
Hi
Why can't you try Dijkstra's algorithm?
Reply With Quote Quick reply to this message  
•
•
Join Date: Dec 2007
Posts: 21
Reputation: Blondeamon is an unknown quantity at this point 
Solved Threads: 0
Blondeamon's Avatar
Blondeamon Blondeamon is offline Offline
Newbie Poster

Re: Need advice on shortest path algorithms

 
0
  #4
May 7th, 2008
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 ?
Reply With Quote Quick reply to this message  
•
•
Join Date: Dec 2006
Posts: 1,089
Reputation: vijayan121 is a name known to all vijayan121 is a name known to all vijayan121 is a name known to all vijayan121 is a name known to all vijayan121 is a name known to all vijayan121 is a name known to all 
Solved Threads: 164
vijayan121 vijayan121 is offline Offline
Veteran Poster

Re: Need advice on shortest path algorithms

 
0
  #5
May 7th, 2008
> 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.
Reply With Quote Quick reply to this message  
•
•
Join Date: Dec 2007
Posts: 21
Reputation: Blondeamon is an unknown quantity at this point 
Solved Threads: 0
Blondeamon's Avatar
Blondeamon Blondeamon is offline Offline
Newbie Poster

Re: Need advice on shortest path algorithms

 
0
  #6
May 8th, 2008
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 ?


C++ Syntax (Toggle Plain Text) 
  1. for (i = 0; i < N - 1; ++i)  
  2.   {		
  3.          for (j = 0; j < M; ++j) 
  4. 		 { //checking neighbohours about minimum cost to jump to
  5.              if (label[E[j].u] > label[E[j].v] + E[j].weight  )  
  6.              {
  7.                 label[E[j].u] =   E[j].weight + label[E[j].v];
  8. 				parent[E[j].u]=E[j].v;  //setting parents if accepted
  9. 			 }
  10. 		}
  11.   }

N is the number of vertices , M is the size of the label array.
Reply With Quote Quick reply to this message  
•
•
Join Date: Dec 2006
Posts: 1,089
Reputation: vijayan121 is a name known to all vijayan121 is a name known to all vijayan121 is a name known to all vijayan121 is a name known to all vijayan121 is a name known to all vijayan121 is a name known to all 
Solved Threads: 164
vijayan121 vijayan121 is offline Offline
Veteran Poster

Re: Need advice on shortest path algorithms

 
0
  #7
May 8th, 2008
> 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.
Reply With Quote Quick reply to this message  
•
•
Join Date: Dec 2007
Posts: 21
Reputation: Blondeamon is an unknown quantity at this point 
Solved Threads: 0
Blondeamon's Avatar
Blondeamon Blondeamon is offline Offline
Newbie Poster

Re: Need advice on shortest path algorithms

 
0
  #8
May 8th, 2008
Perfect , i'll start right away and post my progress when done.

Thanks for the help mate
Reply With Quote Quick reply to this message  
•
•
Join Date: Dec 2007
Posts: 21
Reputation: Blondeamon is an unknown quantity at this point 
Solved Threads: 0
Blondeamon's Avatar
Blondeamon Blondeamon is offline Offline
Newbie Poster

Re: Need advice on shortest path algorithms

 
0
  #9
May 13th, 2008
And here it is:




C++ Syntax (Toggle Plain Text) 
  1. void BellmanFord(Edge E[], int N, long M, int start, int end)
  2. {
  3.      int i = 0, j = 0;
  4.  
  5.      /*                Memory Allocations               */
  6.      if ((l=(int *)malloc(N*sizeof(int))) == NULL)
  7.      {
  8.                  fprintf(stderr, "Out of memory!\n");
  9.                  exit(1);
  10.      }
  11.      if((p=(int *)malloc(N*sizeof(int))) == NULL)
  12.      {
  13.                 fprintf(stderr, "Out of memory!\n");
  14.                 exit(1);
  15.      }
  16.      /*             End of Memory Allocations            */
  17.  
  18.  
  19.  
  20.      for(i = 0 ; i < N ; i++)
  21.      {
  22.            l[i] = 10000000; 
  23.            p[i] = NILL; 
  24.      }// end for
  25.  
  26.      l[start] = E[start].vertex_weight;
  27.                                        E[start].vertex_weight
  28.  
  29.      for(i = start; i < N-1; i++)//Bellman Ford
  30.      {
  31.            for (j = 0; j < M; j++)
  32.            {
  33.                if (l[E[j].u] > l[E[j].v] + E[j].weight)//found better path
  34.                {
  35.                  //set label
  36.                  l[E[j].u] = l[E[j].v] + E[j].weight + E[E[j].u].vertex_weight;
  37.                  //set parent
  38.                  p[E[j].u] = E[j].v;
  39.  
  40.                }//end if
  41.            }//end for
  42.      }//end for
  43.  
  44.      if (l[end] == 10000000)
  45.      {
  46.                 printf("\n\nCannot reach target node!!!\n\n");
  47.                 return 0;
  48.      }
  49.      else
  50.      {
  51.                 printf("\nThe path's weight is... %d", l[end]);
  52.      }
  53.  
  54.      printf("\nThe path is...");
  55.  
  56.      int temp_vertex = end;
  57.      while(p[temp_vertex] != start)
  58.      {
  59.                       printf("(%d, %d) ",p[temp_vertex], temp_vertex);
  60.                       temp_vertex = p[temp_vertex];	 
  61.      }
  62.      printf("(%d, %d) ",p[temp_vertex], temp_vertex);
  63.      printf("\n");
  64.  
  65.      //freeing memory
  66.      free(l);
  67.      free(p);
  68.  
  69.      return 0;
  70. }







Just in case someone needs it
Last edited by Blondeamon; May 13th, 2008 at 3:54 pm.
Reply With Quote Quick reply to this message  
Reply

Quick Reply to Thread
This thread is more than three months old.
Perhaps start a new thread instead?
•
•
•
•
•
•
•
•
Message:
•
•
•
•



Other Threads in the C++ Forum
Thread Tools Search this Thread



api array arrays based beginner binary bitmap c++ c/c++ calculator char char* class code coding compile compiler console conversion count data database delete deploy developer dll download dynamiccharacterarray email encryption error file forms fstream function functions game getline givemetehcodez graph gui homeworkhelp homeworkhelper iamthwee ifstream input int integer java lib linker list loop looping loops map math matrix memory multiple news node number numbertoword output parameter pointer problem program programming project proxy python random read recursion recursive reference rpg sorting string strings struct temperature template text text-file tree url variable vector video visual visualstudio win32 windows winsock word wordfrequency wxwidgets
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC