利用graphshortestpath 可以求最短路径,具体用法参考MATLAB帮助
S=[1 1 2 2 3 3 4 4 4 4 5 6 6 7 8]; %起始节点向量 E=[2 3 5 4 4 6 5 7 8 6 7 8 9 9 9]; %终止节点向量 W=[1 2 12 6 3 4 4 15 7 2 7 7 15 3 10]; %边权值向量,有向图,G(9,9)=0; 9个节点 G=sparse(S,E,W); %关联矩阵的稀疏矩阵表示 G(9,9)=0; P=biograph(G,[],'ShowWeights','on');%建立有向图对象P H=view(P);%显示各个路径权值 [Dist,Path]=graphshortestpath(G,1,9,'Method','Dijkstra') %求节点1到节点9的最短路径 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',2.0);
以下是运行结果,节点1到节点9的最短路径为19
Dist = 19 Path = 1 3 4 5 7 9
利用graphallshortestpaths可以求出所有最短路径
Dists=graphallshortestpaths(G) %求所有最短路径
Dists = 0 1 2 5 9 6 16 12 19 Inf 0 Inf 6 10 8 17 13 20 Inf Inf 0 3 7 4 14 10 17 Inf Inf Inf 0 4 2 11 7 14 Inf Inf Inf Inf 0 Inf 7 Inf 10 Inf Inf Inf Inf Inf 0 Inf 7 15 Inf Inf Inf Inf Inf Inf 0 Inf 3 Inf Inf Inf Inf Inf Inf Inf 0 10 Inf Inf Inf Inf Inf Inf Inf Inf 0
注意一点的是创建稀疏矩阵的时候,如果原始是m*3的矩阵a,分别表示起点、终点和权值,有n个点,用sparse(a),创建的还是m*3,这样根本不对,因为矩阵值是第三列,这样的话矩阵值包括了下标。应该是sparse(a(:,1),a(:,2),a(:,3)),这样的话是max(第一列)*max(第二列)的矩阵,然后设置spraseGraph(n,n)=0,这样的话sparseGraph才是方阵,采用调用系统的最短路径函数。
clc clear all a = [6 1 1 6 4 1 6 5 1 1 2 1 2 3 1 2 4 1 3 5 1 4 5 1]; res = []; graph = sparse(a(:,1),a(:,2),a(:,3)); graph(6,6) = 0; P=biograph(graph,[],'ShowWeights','on');%建立有向图对象P H=view(P);%显示各个路径权值
时间: 2024-09-20 08:14:43