Advertisement
Guest User

Untitled

a guest
Apr 17th, 2014
49
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.96 KB | None | 0 0
  1. function [ DIST, PATH ] = graphkshortestpaths( G, S, T, K )
  2. %
  3. % [ DIST, PATH ] = graphkshortestpaths( G, S, T, K ) determines the K shortest paths from node S
  4. % to node T. weights of the edges are all positive entries in the n-by-n adjacency matrix
  5. % represented by the sparse matrix G. DIST are the K distances from S to T; PATH is a cell array
  6. % with the K shortest paths themselves.
  7. %
  8. % the shortest path algorithm used is Dijkstra's algorithm (graphshortestpath).
  9. %
  10. % **Please note that the algorithm implemented here is an undirected version of Yen's algorithm**
  11. %
  12. % - Yen, JY. Finding the k shortest loopless paths in a network; Management Science 17(11):712-6.
  13. %
  14. % 03/01/2013: I would like to thank Oskar Blom Gransson for helping me find a bug in the previous version.
  15.  
  16. % find A^1
  17. [ DIST( 1 ), PATH{1} ] = graphshortestpath( G, S, T );
  18.  
  19. candidate_paths = { }; % list of candidate paths
  20. candidate_dists = [ ]; % distance of each candidate path
  21.  
  22. % find A^2 ... A^K
  23. for k = 2:K
  24. k_G = G; % version of G used in this iteration (some edges will be removed)
  25.  
  26. % for each node travelled in A^{k-1}
  27. for i = 1:( length( PATH{k-1} ) - 1 )
  28. i_node = PATH{k-1}( i );
  29.  
  30. % iterate over all previous paths and examine if 1..i overlaps with A^{k-1}
  31. for j = 1:k-1
  32. if( length( PATH{j} ) >= i & ( all( PATH{j}( 1:i ) == PATH{k-1}( 1:i ) ) ) )
  33. % it does; remove the following edge that appears in A^j
  34. j_next_node = PATH{j}( i+1 );
  35. k_G( i_node, j_next_node ) = 0; k_G( j_next_node, i_node ) = 0;
  36. end
  37. end
  38.  
  39. % calculate shortest path from i to T
  40. [ dist_i_t, path_i_t ] = graphshortestpath( k_G, i_node, T );
  41. % if path exists, concatenate with 1..i-1 and add to candidates list
  42. if( dist_i_t < Inf )
  43. path_1_i_t = [ PATH{k-1}( 1:i-1 ) path_i_t ];
  44. dist_1_i_t = graphpathdistance( G, path_1_i_t ); % we can safely use G- removed
  45. % edges will not appear
  46. % add resulting path to candidates list
  47. candidate_paths{end+1} = path_1_i_t;
  48. candidate_dists( end+1 ) = dist_1_i_t;
  49. end
  50. end
  51.  
  52. % no candidates; all shortest paths found
  53. if( isempty( candidate_dists ) )
  54. return
  55. end
  56.  
  57. % take shortest path from candidates list as kth path
  58. [ y, i ] = sort( candidate_dists );
  59. DIST( k ) = candidate_dists( i( 1 ) );
  60. PATH{k} = candidate_paths{i( 1 )};
  61. % remove shortest path (and all of its copies) from the candidates list
  62. remove_indices = [];
  63. for idx = 1:length( candidate_paths )
  64. if( length( PATH{k} ) == length( candidate_paths{idx} ) & all( PATH{k} == candidate_paths{idx} ) )
  65. remove_indices( end+1 ) = idx;
  66. end
  67. end
  68. candidate_dists( remove_indices ) = [];
  69. candidate_paths( remove_indices ) = [];
  70. end
  71.  
  72.  
  73. function DIST = graphpathdistance( G, PATH )
  74. %
  75. % DIST = graphpathdistance( PATH ) calculates the distance travelled by PATH in graph G.
  76.  
  77. % convert PATH into edges
  78. edges = sub2ind( size( G ), PATH( 1:end-1 ), PATH( 2:end ) );
  79. % sum weights over edges
  80. DIST = full( sum( G( edges ) ) );
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement