How to compute directed graph diameter in C++ -


this question has answer here:

i have directed graph given matrix , need write program (c++) computes it's diameter. i'm lost when comes this. there known algorithm this? \

how think should go:

  • convert undirected graph (for directedmatrix[i][j] !=0 , 1 nrnodes , j i+1 nrnodes, make matrix[j][i]=matrix[i][j]=directedmatrix[i][j])
  • compute max distance 2 nodes ( distacematrix[i][j] = max distance node node j; distancematrix[i][i] = min)
  • find maxim value above matrix , that's our answer.

thoughts , optimizations?

assuming number of nodes not great, simple solution use floyd-warshall algorithm find shortest paths between pairs of nodes , take greatest one. following code demonstrates it:

#include <cstdio>  using namespace std;  #define max 107 #define not_connected -1  int distance[max][max];  //number of nodes int nodescount;  //initialize distances  void initialize(){     (int i=0;i<max;++i){         (int j=0;j<max;++j){             distance[i][j]=not_connected;         }         distance[i][i]=0;     } }  int main(){      initialize();      //get nodes count     scanf("%d", &nodescount);      //edges count     int m;     scanf("%d", &m);      while(m--){         //nodes - let indexation begin 1         int a, b;          //edge weight         int c;          scanf("%d %d %d", &a, &b, &c);         distance[a][b]=c;     }      //floyd-warshall     (int k=1;k<=nodescount;++k){         (int i=1;i<=nodescount;++i){             if (distance[i][k]!=not_connected){                 (int j=1;j<=nodescount;++j){                     if (distance[k][j]!=not_connected && (distance[i][j]==not_connected || distance[i][k]+distance[k][j]<distance[i][j])){                         distance[i][j]=distance[i][k]+distance[k][j];                     }                 }             }         }     }      int diameter=-1;      //look distant pair     (int i=1;i<=nodescount;++i){         (int j=1;j<=nodescount;++j){             if (diameter<distance[i][j]){                 diameter=distance[i][j];                 printf("%d %d\n", i, j);             }         }     }      printf("%d\n", diameter);      return 0; }

Comments

Post a Comment

Popular posts from this blog

apache - Remove .php and add trailing slash in url using htaccess not loading css -

i have add following code htaccess file removing .php extension , add trailing slash urls. worked fine reduced page loading speed , css code not loading @ all. pages ugly. please help rewriteengine on rewritebase / ## hide .php extension snippet # externally redirect /dir/foo.php /dir/foo rewritecond %{the_request} ^[a-z]{3,}\s([^.]+)\.php [nc] rewriterule ^ %1/ [r,l] # add trailing slash rewritecond %{request_filename} !-f rewritecond %{request_uri} !/$ rewriterule . %{request_uri}/ [l,r=301] # internally forward /dir/foo /dir/foo.php rewritecond %{request_filename} !-d rewritecond %{request_filename}.php -f rewriterule ^(.*?)/?$ $1.php [l] we can rewrite urls using .htaccess files. before writing in .htaccess files need verify kind of server using. can check server adding a <?php phpinfo(); ?> in php page. ensure mod_rewrite module enabled in apache server. can identified checking phpinfo included page. common methods used url rewriting follows ...
Read more

javascript - jQuery show full size image on click -

pretty self explanatory not workking . i want display full image when user click on image... yes know there tons of plugins but i want keep simple. any idea ? css : .full { display: none; width: 500px; height: 500px; margin-left: 100px; margin-top: -300px; position: fixed; background-color: #f00; z-index: 6; } .thumbnail { width: 50px; height: 50px; } html: <img class="thumbnail" src="http://4.bp.blogspot.com/-uhbdp2esxng/txneptvi92i/aaaaaaaaaky/upfqis7zto0/s1600/rihanna-wallpaper.jpg"> jquery: $(document).ready(function() { $('.thumbnail').on('click', function() { var img = $('<img />',{src:this.src,'class':'full'}); $('.full').html(img).show(); console.log('done!'); }); }); try looking how jquery works. $(document).ready(function() { $('.thumbnail').on('click', function(...
Read more