图论工具箱

非常全的图论工具箱，含有最短路、生成树等一些列问题的解决函数代码和说明！

function [DP] = all_shortest_paths（Avarargin）
% all_shortest_paths Compute the weighted all pairs shortest path problem.
%
% D = all_shortest_paths（A） returns the distance matrix D for all vertices
% where D（ij） indicates the shortest path distance between vertex i and
% vertex j.  
%
% For the Floyd-Warshall algorithm this function can return the 
% predecessor matrix as well:
%   [D P]=all_shortest_paths（Astruct（‘algname‘‘floyd_warshall‘））;
% returns P so that the P（ij） is the node preceeding j on the path from
% i to j.  To build the path between （ij） use the commands
%   p=[]; while j~=0 p（end+1）=j; j=P（ij）; end; p=fliplr（p）;
% 
% ... = all_shortest_paths（Au...） takes a set of
% key-value pairs or an options structure.  See set_matlab_bgl_options
% for the standard options. 
%   options.algname: the algorithm to use 
%       [{‘auto‘} | ‘johnson‘ | ‘floyd_warshall‘]
%   options.inf: the value to use for unreachable vertices 
%       [double > 0 | {Inf}]
%   options.edge_weight: a double array over the edges with an edge
%       weight for each node see EDGE_INDEX and EXAMPLES/REWEIGHTED_GRAPHS
%       for information on how to use this option correctly
%       [{‘matrix‘} | length（nnz（A）） double vector]
%
% Note: ‘auto‘ cannot be used with ‘nocheck‘ = 1.  The ‘auto‘ algorithms
% checks the number of edges in A and if the graph is more than 10% dense
% it uses the Floyd-Warshall algorithm instead of Johnson‘s algorithm.
%
% Example:
%    load graphs/clr-26-1.mat
%    all_shortest_paths（A）
%    all_shortest_paths（Astruct（‘algname‘‘johnson‘））
%
% See also JOHNSON_ALL_SP FLOYD_WARSHALL_ALL_SP.

% David Gleich
% Copyright Stanford University 2006-2008

%% History
%  2006-04-19: Initial version
%  2006-05-31: Added full2sparse check
%  2007-03-01: Added option for predecessor matrix from floyd_warshall
%  2007-04-20: Added edge weight option
%  2007-07-08: Fixed typos in strings and documentation
%    Removed fixes for the Johnson algorithm
%  2007-07-12: Fixed edge_weight documentation.
%  2007-07-21: Fixed divide by 0 error in check for algorithm type
%  2008-04-02: Added documenation for predecessor matrix
%  2008-10-07: Changed options parsing
%%

[trans check full2sparse] = get_matlab_bgl_options（varargin{:}）;
if full2sparse && ~issparse（A） A = sparse（A）; end

options = struct（‘algname‘ ‘auto‘ ‘inf‘ Inf ‘edge_weight‘ ‘matrix‘）;
options = merge_options（optionsvarargin{:}）;

% edge_weights is an indicator that is 1 if we are using edge_weights
% passed on the command line or 0 if we are using the matrix.
%edge_weights = 0;
edge_weight_opt = ‘matrix‘;

if strcmp（options.edge_weight ‘matrix‘）
    % do nothing if we are using the matrix weights
else
    edge_weight_opt = options.edge_weight;
end

if check
    % check the values of the matrix
    check_matlab_bgl（Astruct（‘values‘1））;
    
    % set the algname
    if strcmpi（options.algname ‘auto‘）
        nz = nnz（A）;
        if （nz/（numel（A）+1） > .1）
            opti

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2012-06-11 15:48  matlab_bgl\
     文件         208  2008-10-22 09:37  matlab_bgl\.project
     目录           0  2012-06-11 15:48  matlab_bgl\@inplace\
     文件         245  2008-10-22 09:37  matlab_bgl\@inplace\assign.m
     文件         195  2008-10-22 09:37  matlab_bgl\@inplace\display.m
     文件         319  2008-10-22 09:37  matlab_bgl\@inplace\double.m
     文件         239  2008-10-22 09:37  matlab_bgl\@inplace\end.m
     文件         766  2008-10-22 09:37  matlab_bgl\@inplace\inplace.m
     文件         228  2008-10-22 09:37  matlab_bgl\@inplace\size.m
     文件         269  2008-10-22 09:37  matlab_bgl\@inplace\subsasgn.m
     文件         687  2008-10-22 09:37  matlab_bgl\@inplace\subsref.m
     目录           0  2012-06-11 15:48  matlab_bgl\@ipdouble\
     文件         276  2008-10-22 09:37  matlab_bgl\@ipdouble\ipdouble.m
     目录           0  2012-06-11 15:48  matlab_bgl\@ipint32\
     文件         269  2008-10-22 09:37  matlab_bgl\@ipint32\ipint32.m
     文件        4560  2008-10-22 09:37  matlab_bgl\Contents.m
     文件        3546  2008-10-22 09:37  matlab_bgl\all_shortest_paths.m
     文件        1568  2008-07-09 17:39  matlab_bgl\approx_multiway_cut.m
     文件        3582  2008-10-22 09:37  matlab_bgl\astar_search.m
     文件        1606  2008-10-22 09:37  matlab_bgl\bellman_ford_sp.m
     文件        3525  2008-10-22 09:37  matlab_bgl\betweenness_centrality.m
     文件        1757  2008-10-22 09:37  matlab_bgl\bfs.m
     文件        2198  2008-10-22 09:37  matlab_bgl\biconnected_components.m
     文件        1850  2008-10-22 09:37  matlab_bgl\boyer_myrvold_planarity_test.m
     文件        2525  2008-10-22 09:37  matlab_bgl\breadth_first_search.m
     文件        1728  2008-10-22 09:37  matlab_bgl\chrobak_payne_straight_line_drawing.m
     文件         774  2008-10-22 09:37  matlab_bgl\circle_graph_layout.m
     文件        1347  2008-10-22 09:37  matlab_bgl\clique_graph.m
     文件        3653  2008-10-22 09:37  matlab_bgl\clustering_coefficients.m
     文件        3048  2008-10-22 09:37  matlab_bgl\combine_visitors.m
     文件        1416  2008-10-22 09:37  matlab_bgl\components.m
............此处省略607个文件信息