Posted By

ldominov on 01/16/13


Tagged


Versions (?)

ona dvojica


 / Published in: C++
 

ona dvojica za koje mi je bila mrska implementacija....

  1. /* Warshall-floyd algorithm
  2.  *
  3.  * Shortest path between all pairs of vertices
  4.  * strategy: dynamic programming
  5.  * order: n **3
  6.  */
  7.  
  8. #include <limits.h>
  9. #include <stdio.h>
  10.  
  11. typedef int adj_matrix [10][10];
  12.  
  13. #define MAX_VERTEX 9
  14.  
  15. #define FOUND 0
  16.  
  17. adj_matrix gr = {
  18. { 0, 5, 3, INT_MAX, 2 },
  19. { INT_MAX, 0, 2, 6, INT_MAX },
  20. { INT_MAX, 1, 0, 2, INT_MAX },
  21. { INT_MAX, INT_MAX, INT_MAX, 0, INT_MAX },
  22. { INT_MAX, 6, 10, 4, 0 }
  23. };
  24. // This directed graph has five vertices.
  25.  
  26. #define NUM_VERT 5
  27. // as on gr
  28.  
  29. char first_hop[NUM_VERT][NUM_VERT];
  30. // first_hop[i][j] contains the first hop in the path between i and j
  31.  
  32.  
  33. void warshall() {
  34.  
  35. int k,i,j;
  36. int hopdist;
  37.  
  38. for( k = 0; k < NUM_VERT; k ++ ) {
  39.  
  40. for( i = 0; i < NUM_VERT; i ++ ) { // row index
  41.  
  42. for( j = 0; j < NUM_VERT; j ++ ) { // column index
  43.  
  44. if(gr[i][k] == INT_MAX || gr[k][j] == INT_MAX )
  45. hopdist = INT_MAX;
  46. else // can hop to k
  47. hopdist = gr[i][k] + gr[k][j];
  48.  
  49. if( hopdist < gr[i][j]) { // if hopping to k is better
  50. first_hop[i][j] = k; // if you want to go from i to j then first go to k
  51. gr[i][j] = hopdist;
  52. }
  53. }
  54. }
  55. }
  56. }
  57.  
  58.  
  59. void print_first_hop() {
  60.  
  61. int i,j;
  62. for( i = 0; i < NUM_VERT; i ++ ) {
  63. for( j = 0 ; j < NUM_VERT; j ++ )
  64. printf("%d ",first_hop[i][j]);
  65.  
  66. printf("\n");
  67. }
  68.  
  69. }
  70.  
  71. int main() {
  72.  
  73. int i, j;
  74. for( i = 0; i < NUM_VERT; i ++ ) {
  75.  
  76. for( j = 0; j < NUM_VERT; j ++ ) {
  77.  
  78. if( gr[i][j] != INT_MAX ) // if edge exists
  79. first_hop[i][j] = j;
  80. else first_hop[i][j] = -1; // not known yet
  81. }
  82.  
  83. }
  84. warshall();
  85. printf("the first hop in the shortest path from any vertex i to j is \n");
  86. print_first_hop();
  87. }

Report this snippet  

You need to login to post a comment.