用MATLAB软件如何找最短路径?
发布网友
发布时间：2023-02-15 01:17
共1个回答
热心网友
时间：2023-09-13 16:33
graphshortestpath solves the shortest path problem in graph.
[DIST,PATH,PRED] = graphshortestpath(G,S) determines the single source
shortest paths from node S to all other nodes in the graph G. Weights of
the edges are all nonzero entries in the n-by-n adjacency matrix
represented by the sparse matrix G. DIST are the n distances from source
to every node (using Inf for non-reachable nodes and zero for the source
node). The PATH contains the winning paths to every node, and PRED
contains the predecessor nodes of the winning paths.
[DIST,PATH,PRED] = graphshortestpath(G,S,D) determines the single
source-single destination shortest path from node S to node D.
graphshortestpath(...,'METHOD',METHOD) selects the algorithm to use,
options are:
'BFS' - Breadth First Search, assumes all the weights are
equal, edges are nonzero entries in the sparse matrix
G. Time complexity is O(n+e).
['Dijkstra'] - Assumes that weights of the edges are all positive
values in the sparse matrix G. Time complexity is
O(log(n)*e).
'Bellman-Ford' - Assumes that weights of the edges are all nonzero
entries in the sparse matrix G. Time complexity is
O(n*e).
'Acyclic' - The input graph must be acyclic. Assumes that weights
of the edges are all nonzero entries in the sparse
matrix G. Time complexity is O(n+e).
Note: n and e are number of nodes and edges respectively.
graphshortestpath(...,'DIRECTED',false) indicates that the graph G is
undirected, upper triangle of the sparse matrix is ignored. Default is
true.
graphshortestpath(...,'WEIGHTS',W) provides custom weights for the edges,
useful to indicate zero valued weights. W is a column vector with one
entry for every edge in G, traversed column-wise.
Examples:
% Create a directed graph with 6 nodes and 11 edges
W = [.41 .99 .51 .32 .15 .45 .38 .32 .36 .29 .21];
DG = sparse([6 1 2 2 3 4 4 5 5 6 1],[2 6 3 5 4 1 6 3 4 3 5],W)
h = view(biograph(DG,[],'ShowWeights','on'))
% Find shortest path from 1 to 6
[dist,path,pred] = graphshortestpath(DG,1,6)
% Mark the nodes and edges of the shortest path
set(h.Nodes(path),'Color',[1 0.4 0.4])
edges = getedgesbynodeid(h,get(h.Nodes(path),'ID'));
set(edges,'LineColor',[1 0 0])
set(edges,'LineWidth',1.5)
% Solving the previous problem for an undirected graph
UG = tril(DG + DG')
h = view(biograph(UG,[],'ShowArrows','off','ShowWeights','on'))
% Find the shortest path between node 1 and 6
[dist,path,pred] = graphshortestpath(UG,1,6,'directed',false)
% Mark the nodes and edges of the shortest path
set(h.Nodes(path),'Color',[1 0.4 0.4])
fowEdges = getedgesbynodeid(h,get(h.Nodes(path),'ID'));
revEdges = getedgesbynodeid(h,get(h.Nodes(fliplr(path)),'ID'));
edges = [fowEdges;revEdges];
set(edges,'LineColor',[1 0 0])
set(edges,'LineWidth',1.5)
See also: graphallshortestpaths, graphconncomp, graphisdag,
graphisomorphism, graphisspantree, graphmaxflow, graphminspantree,
graphpred2path, graphtheorydemo, graphtopoorder, graphtraverse.
References:
[1] E.W. Dijkstra "A note on two problems in connexion with graphs"
Numerische Mathematik, 1:269-271, 1959.
[2] R. Bellman "On a Routing Problem" Quarterly of Applied Mathematics,
16(1):87-90, 1958.
Reference page in Help browser
doc graphshortestpath
