查看: 22823|回复: 38|关注: 0
Matlab中图论求最短路径之Dijkstra
<h1 style="color:# 麦片财富积分
新手, 积分 16, 距离下一级还需 34 积分
关注者： 2
1.jpg (20.11 KB, 下载次数: 928)
10:22 上传
其邻接矩阵为：A =
& &&&0& &&&2& &&&8& &&&1& &Inf& &Inf& &Inf& &Inf
& &&&2& &&&0& &&&6& &Inf& &&&1& &Inf& &Inf& &Inf
& &&&8& &&&6& &&&0& &&&7& &&&5& &&&1& &&&2& &Inf
& &&&1& &Inf& &&&7& &&&0& &Inf& &Inf& &&&9& &Inf
& &Inf& &&&1& &&&5& &Inf& &&&0& &&&3& &Inf& &&&8
& &Inf& &Inf& &&&1& &Inf& &&&3& &&&0& &&&4& &&&6
& &Inf& &Inf& &&&2& &&&9& &Inf& &&&4& &&&0& &&&3
& &Inf& &Inf& &Inf& &Inf& &&&8& &&&6& &&&3& &&&0复制代码算法基本思想
& & 　设S为最短距离已确定的顶点集（看作红点集），V-S是最短距离尚未确定的顶点集（看作蓝点集）。
& & 　初始化时，只有源点s的最短距离是已知的(SD(s)=0)，故红点集S={s}，蓝点集为空。
②重复以下工作，按路径长度递增次序产生各顶点最短路径
& & 　在当前蓝点集中选择一个最短距离最小的蓝点来扩充红点集，以保证算法按路径长度递增的次序产生各顶点的最短路径。
& & 　当蓝点集中仅剩下最短距离为∞的蓝点，或者所有蓝点已扩充到红点集时，s到所有顶点的最短路径就求出来了。
& & 　①若从源点到蓝点的路径不存在，则可假设该蓝点的最短路径是一条长度为无穷大的虚拟路径。
& & 　②从源点s到终点v的最短路径简称为v的最短路径；s到v的最短路径长度简称为v的最短距离，并记为SD(v)。
在蓝点集中选择一个最短距离最小的蓝点k来扩充红点集
& & 　根据按长度递增序产生最短路径的思想，当前最短距离最小的蓝点k的最短路径是：
& & 　源点，红点1，红点2，…，红点n，蓝点k
距离为：源点到红点n最短距离+&红点n,蓝点k&边长
& & 　为求解方便，设置一个向量D[0．．n-1]，对于每个蓝点v∈ V-S，用D[v]记录从源点s到达v且除v外中间不经过任何蓝点(若有中间点，则必为红点)的&最短&路径长度（简称估计距离）。
& & 　若k是蓝点集中估计距离最小的顶点，则k的估计距离就是最短距离，即若D[k]=min{D i∈V-S}，则D[k]=SD(k)。
& & 　初始时，每个蓝点v的D[c]值应为权w&s，v&，且从s到v的路径上没有中间点，因为该路径仅含一条边&s，v&。
& & 　在蓝点集中选择一个最短距离最小的蓝点k来扩充红点集是Dijkstra算法的关键
k扩充红点集s后，蓝点集估计距离的修改
& & 　将k扩充到红点后，剩余蓝点集的估计距离可能由于增加了新红点k而减小，此时必须调整相应蓝点的估计距离。
& & 　对于任意的蓝点j，若k由蓝变红后使D[j]变小，则必定是由于存在一条从s到j且包含新红点k的更短路径：P=&s，…，k，j&。且D[j]减小的新路径P只可能是由于路径&s，…，k&和边&k，j&组成。
& & 　所以，当length(P)=D[k]+w&k，j&小于D[j]时，应该用P的长度来修改D[j]的值。
Matlab程序：function [distance,path]=dijkstra(A,s,e)
% A: adjcent matrix
% s: start node
% e: end node
% [distance,path]=dijkstra(A,s,e)
% return the distance and path between the start node and the end node.
% initialize
n=size(A,1);& && &&&% node number
D=A(s,:);& && && &&&% distance vector
path=[];& && && && &% path vector
visit=ones(1,n);& & % node visibility
visit(s)=0;& && && &% source node is unvisible
parent=zeros(1,n);&&% parent node
% the shortest distance
for i=1:n-1& && && &% BlueSet has n-1 nodes
& & temp=[];
& & for j=1:n
& && &&&if visit(j)
& && && && &temp=[temp D(j)];
& && &&&else
& && && && &temp=[temp inf];
& && &&&end
& & end
& & [value,index]=min(temp);
& & j= visit(j)=0;
& & for k=1:n
& && &&&if D(k)&D(j)+A(j,k)
& && && && &D(k)=D(j)+A(j,k);
& && && && &parent(k)=j;
& && &&&end
& & end
end
distance=D(e);
% the shortest distance path
if parent(e)==0, end
% there is a shortest distance path
t=e; path=t;
while t~=s && t&0
& & p=parent(t);
& & path=[p path];
& & t=p;
end
path(1)=s;
& & 复制代码有2个警告 ‘temp’ might be growing inside a loop. Consider preallocating for speed复制代码这样用的方便 但是不怎么规范，不晓得怎么改
[ 本帖最后由 mooni 于
10:31 编辑 ]
<h1 style="color:# 麦片财富积分
不错，可以运行，希望大家多交流一些常用算法
<h1 style="color:# 麦片财富积分
数模刚好用上
<h1 style="color:# 麦片财富积分
关注者： 1
matlab中有自带的算法，既适用于稀疏图也可用于稠密图。
&& help graphshortestpath
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
&&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 = [fowErevEdges];
& & 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
<h1 style="color:# 麦片财富积分
关注者： 1
用graphshortestpath处理上面的问题如下：
& &&&0& &&&2& &&&8& &&&1& &Inf& &Inf& &Inf& &Inf
& &&&2& &&&0& &&&6& &Inf& &&&1& &Inf& &Inf& &Inf
& &&&8& &&&6& &&&0& &&&7& &&&5& &&&1& &&&2& &Inf
& &&&1& &Inf& &&&7& &&&0& &Inf& &Inf& &&&9& &Inf
& &Inf& &&&1& &&&5& &Inf& &&&0& &&&3& &Inf& &&&8
& &Inf& &Inf& &&&1& &Inf& &&&3& &&&0& &&&4& &&&6
& &Inf& &Inf& &&&2& &&&9& &Inf& &&&4& &&&0& &&&3
& &Inf& &Inf& &Inf& &Inf& &&&8& &&&6& &&&3& &&&0];
&& A(isinf(A))=0;
&& [d,p,pred]=graphshortestpath(sparse(A),1)
& &&&0& &&&2& &&&7& &&&1& &&&3& &&&6& &&&9& & 11
&&Columns 1 through 6
& & [1]& & [1x2 double]& & [1x5 double]& & [1x2 double]& & [1x3 double]& & [1x4 double]
&&Columns 7 through 8
& & [1x6 double]& & [1x4 double]
& &&&0& &&&1& &&&6& &&&1& &&&2& &&&5& &&&3& &&&5
<h1 style="color:#2 麦片财富积分
不知何许人也~
关注者： 300
回复 1# brumegoo 的帖子
恩.好.虽说是经典的东西.
[url=.cn/faruto][color=red]孤单是一个人的狂欢狂欢是一群人的孤单[/color][/url] [url=/thread-.html]神经网络30个案例分析[/url]
<h1 style="color:# 麦片财富积分
temp这个矩阵元素的个数会不断增长
你事先定义一下它的大小，就好了
<h1 style="color:# 麦片财富积分
关注者： 2
这段时间有点事情 很久没有逛论坛了 谢谢大家的回复 那段程序我前段时间该了下 temp和path的长度是不确定的，只能估计一个值
Matlab里面的确是有自带的函数可以解，我不是为了解决一个问题，只是练习编写Matlab程序
改过的程序 把2个警告去掉了function [distance,path]=dijkstra(A,s,e)
% [DISTANCE,PATH]=DIJKSTRA(A,S,E)
% returns the distance and path between the start node and the end node.
%
% A: adjcent matrix
% s: start node
% e: end node
% initialize
n=size(A,1);& && &&&% node number
D=A(s,:);& && && &&&% distance vector
path=[];& && && && &% path vector
visit=ones(1,n);& & % node visibility
visit(s)=0;& && && &% source node is unvisible
parent=zeros(1,n);&&% parent node
% the shortest distance
for i=1:n-1& && && &% BlueSet has n-1 nodes
& & temp=zeros(1,n);
& & count=0;
& & for j=1:n
& && &&&if visit(j)
& && && && &temp=[temp(1:count) D(j)];
& && &&&else
& && && && &temp=[temp(1:count) inf];
& && &&&end
& && &&&count=count+1;
& & end
& & [value,index]=min(temp);
& & j= visit(j)=0;
& & for k=1:n
& && &&&if D(k)&D(j)+A(j,k)
& && && && &D(k)=D(j)+A(j,k);
& && && && &parent(k)=j;
& && &&&end
& & end
end
distance=D(e);
% the shortest distance path
if parent(e)==0, end
path=zeros(1,2*n);& && &% path preallocation
t=e; path(1)=t; count=1;
while t~=s && t&0
& & p=parent(t);
& & path=[p path(1:count)];
& & t=p; count=count+1;
end
if count&=2*n, error(['The path preallocation length is too short.',...
& && &&&'Please redefine path preallocation parameter.']);
end
path(1)=s;
path=path(1:count);复制代码
<h1 style="color:# 麦片财富积分
写得不错~我刚学matlab 不久，试着写这个程序弄了好久没弄出来！得好好研究下.谢谢楼主~
<h1 style="color:# 麦片财富积分
上面那个那个得出来的最短距离不是经过所有顶点的，倘若要求出经过所有顶点一次且路径最短，那应该怎么算啊？麻烦各位大侠了！
Powered byC++用Dijkstra(迪杰斯特拉)算法求最短路径
投稿：daisy
字体：[ ] 类型：转载 时间：
Dijkstra（迪杰斯特拉）算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。下面这篇文章就给大家介绍关于C++用Dijkstra算法(迪杰斯特拉算法)求最短路径的方法，下面来一起看看吧。
迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。
按路径长度递增次序产生算法：
　把顶点集合V分成两组：
　　（1）S：已求出的顶点的集合（初始时只含有源点V0）
　　（2）V-S=T：尚未确定的顶点集合
　　将T中顶点按递增的次序加入到S中，保证：
　　（1）从源点V0到S中其他各顶点的长度都不大于从V0到T中任何顶点的最短路径长度
　　（2）每个顶点对应一个距离值
　　S中顶点：从V0到此顶点的长度
　　T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度
　　依据：可以证明V0到T中顶点Vk的，或是从V0到Vk的直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和
（1）题目：编写一个校园导游程序，为来访的客人提供各种信息查询服务。
　　　　主要功能：1.设计学校的校园平面图，所含景点不少于10个：顶点表示景点，边表示路径等；
　　　　　　　　　2.为客人提供图中任意景点相关信息的查询；
　　　　　　　　　3.为客人提供图中任意景点的问路查询，即查询人以景点间的一条最短路径。
　　　　　　要求：1.设计一个主界面；
　　　　　　&&&&&&& 2.设计功能菜单，供用户选择
　　　　　　&&&&&&& 3.有一定的实用性。
（2）设计思路：
　　1、该题主要有算法思路以及程序的逻辑思路，首先从逻辑思路讲，进入程序，首先设计一个主菜单，选项有景点信息查询，最短路径查询以及显示景点的平面视图三个子菜单，然后根据用户的输入选择的子菜单前的编号，分进入不同的子菜单；该功能是由if….else if…. 语句实现。在景点信息查询和最短路径查询子菜单下还有二级子菜　单，都是列 出所有景点并在前面编号，查询景点信息时，输入景点前面的编号即可，查询最短路径时，先输入起点的编号，再输入终点的编号。而显示景点视图则调用景点平面图函数即可显 示。
　　2、算法思路主要是迪杰斯特拉算法的思路，利用迪杰斯特拉算法求最短路径。
　　3、先定义好图的储存结构，本题采用邻接矩阵的方式来表示图，并在主函数中初始化该图；
　　4、定义三个全局一维数组，一个bool类型数组S[]用来记录从v0到vi是否已经确定了最短路径，是则记S[i]=true ,否记S[i]= flase；一个int 类型数组Path[]用来记录从v0到vi的当前最短路径上的vi的直接前驱顶点编号，若v 到vi之间有边则记Path[i] = v的编号，否则记Path[i] = -1；最后一个数组D[]用来记录从v0到vi之间的最短路径长度，存在则记v0到vi之间边的权值或者权值和，否则记为MAX
　　5、定义一个求最短路径的函数，传入的参数为图和起点，首先进行初始化工作，初始化S[]数组全为false，D[]数组初始化为起点到各个顶点的权值，Path[]数组初始化为起点是否与各顶点有边，有则记v0否则记-1；
　　6、然后进行n-1次for循环，找出vo到其余n-1个顶点之间的最短路径，比较当前D[]数组中最小值，找到最小值的编号v，该编号就是从v0出发到所有顶点中距离最短的顶点编号，然后把S[v]的值置为true。说明从v0出发到顶点v已经找到最短路径；
　　7、接着就要更新D[]数组，因为D[]数组是记录最短路径的，现在已经找到了一个顶点的最短路径，已该顶点v为中间点，判断从该顶点v出发到剩下的顶点的路径长度加上该点到v0的路径长度是否小于直接从v0出发到其余顶点的路径长度，如果小于，则更新D[i]为以该顶点v为中间点求得的路径长度。更新Path[i] = v；即i的前驱不再是v0而是v;
　　8、循环（6）（7）两步n-1次即可得到D[]数组，输出D[]数组既是v0到所有顶点的最短路径长度；
（3）源代码：
#include&iostream&
#include&fstream&
#include&string&
*作者：Dmego
#define MAX 1000000 //表示极大值∞
#define max 10
bool S[max]; //记录从源点V0到终点Vi是否已经确定为最短路径，确定了记true，否则记false
int Path[max]; //记录从源点V0到终点Vi的当前最短路径上终点Vi的直接前驱顶点序号，若V0到Vi之间有边前驱为V0否则为-1
int D[max]; //记录源点到终点之间最短路径的长度，存在记V0到Vi的边的权值，否则记为MAX
typedef struct
string vexs[max]; //顶点表
int arcs[max][max]; //邻接矩阵
int vexnum, //图当前点数和边数
//利用迪杰斯特拉算法求最短路径
void ShortestPath_DIJ(AMGraph &G, int v0)
{//使用迪杰斯特拉算法求有向网G中的V0 定点到其余顶点的最短路径
int n = G.//顶点数
for (int v = 0; v & v++)//n个顶点依次初始化
S[v] =//S初始化为空集
D[v] = G.arcs[v0][v];//将v0到各个终点的最短路径长度初始化为边上的权值
if (D[v] & MAX)
Path[v] = v0;//如果v0和v之间有边，则将v的前驱初始化为v0
Path[v] = -1;//如果v0和v之间无边，则将v的前驱初始化为-1
S[v0] = //将v0加入s
D[v0] = 0;//源点到源点的权值为0
//---------初始化结束，开始主循环，每次求得v0到某个顶点的最短路径，将v加到S数组
for (int i = 1; i & i++)//依次对其余n-1个顶点进行计算
int min = MAX;
int v = v0;
for (int w = 0; w & w++)
if (!S[w] && D[w] & min)
{//选择一条当前最短路径，终点为v
min = D[w];
S[v] =//将v加到s集合中
for (int w = 0; w & w++)
{//更新从v0出发到集合V-S上所有顶点的最短路径长度
if (!S[w] && (D[v] + G.arcs[v][w] & D[w]))
D[w] = D[v] + G.arcs[v][w];//更新D[w]
Path[w] =//更改w的前驱为v
//背景函数
void backGround()
cout && "|*****************************************************************|" &&
cout && " |------------------------铁大旅游景点图-----------------|" &&
cout && "|*****************************************************************|" &&
cout && "|
单位：米 |" &&
cout && "|
cout && "|
cout && "|
cout && "| ③ 200╱ ╲
cout && "| 西 ↙ ╲ 150
cout && "| 操 ◎
160 ╱ ╲ 200 |" &&
cout && "| 场 ↖150
cout && "| ④ ↘ 140 ↘ 学院 200 基教 ↙ 230 ↘ |" &&
cout && "| 体育馆 ◎-------------→◎←--------------→◎←--------------→◎ |" &&
cout && "|
↗② |" &&
cout && "|
100 ╲ ╱ ╲ 125 ╱ ╲ 150 ╱ 综 |" &&
cout && "|
↘ ↙ 100 ╲ ╱135 ╲ ╱145 餐 |" &&
cout && "|
↘ ↙ |" &&
cout && "|
cout && "|
cout && "|
cout && "|*****************************************************************|" &&
void menu()
cout && "|*****************************************************************|" &&
cout && "|----------------------------铁大导游小程序-----------------------|" &&
cout && " |*********************************************************|" &&
cout && " |--------------------1-景点信息查询--------------|" &&
cout && " |--------------------2-最短路径查询--------------|" &&
cout && " |--------------------3-显示景点视图--------------|" &&
cout && " |-------------------4-退出导游程序------ --------|" &&
cout && "|*****************************************************************|" &&
cout && "&&&请选择：";
//景点信息查询二级菜单
void jmenu()
cout && "|*****************************************************************|" &&
cout && " |-------------------------景点信息查询------------------------|" &&
cout && " |***********************************************************|" &&
cout && " |----------------------1-信息学院介绍-------------------| " &&
cout && " |----------------------2-综合餐厅介绍-------------------| " &&
cout && " |----------------------3-西操场介绍---------------------| " &&
cout && " |----------------------4-体育馆介绍---------------------| " &&
cout && " |----------------------5-春晖楼介绍---------------------| " &&
cout && " |----------------------6-基教介绍-----------------------| " &&
cout && " |----------------------7-九教介绍-----------------------| " &&
cout && " |----------------------8-九栋介绍-----------------------| " &&
cout && " |----------------------9-沁园介绍-----------------------| " &&
cout && " |---------------------10-翠园介绍-----------------------| " &&
cout && "|*****************************************************************|" &&
cout && "&&&请要查询的景点编号：";
//最短路径查询二级菜单
void pmenu()
cout && "|*****************************************************************|" &&
cout && " |-------------------------最短路径查询------------------------|" &&
cout && " |***********************************************************|" &&
cout && " |---------------------1-信息学院-------------------| " &&
cout && " | --------------------2-综合餐厅-------------------| " &&
cout && " |---------------------3-西操场---------------------| " &&
cout && " |---------------------4-体育馆---------------------| " &&
cout && " |---------------------5-春晖楼---------------------| " &&
cout && " |---------------------6-基教-----------------------| " &&
cout && " |---------------------7-九教-----------------------| " &&
cout && " |---------------------8-九栋-----------------------| " &&
cout && " |---------------------9-沁园-----------------------| " &&
cout && " |--------------------10-翠园-----------------------| " &&
cout && "|*****************************************************************|" &&
cout && "&&&请依次输入起点编号和终点编号：";
void main()
//初始化操作
AMGraph amg = { { "信息学院","综合餐厅","西操场","体育馆","春晖楼",
"基教", "九教", "九栋", "沁园", "翠园" },
//-1代表两边不相连，权值无限大
//邻接矩阵 /* 信 综 西 体 春 基 教 栋 沁 翠*/
{{MAX,MAX,MAX,140,MAX,200,150,MAX,100,125 },
{MAX,MAX,MAX,MAX,145,230,MAX,100,MAX,MAX },
{MAX,MAX,MAX,150,MAX,MAX,200,MAX,MAX,MAX },
{140,MAX,150,MAX,MAX,MAX,MAX,MAX,100,MAX },
{MAX,145,MAX,MAX,MAX,150,MAX,MAX,MAX,MAX },
{200,230,MAX,MAX,150,MAX,MAX,160,MAX,135 },
{150,MAX,200,MAX,MAX,MAX,MAX,MAX,MAX,MAX },
{MAX,200,MAX,MAX,MAX,160,MAX,MAX,MAX,MAX },
{100,MAX,MAX,100,MAX,MAX,MAX,MAX,MAX,MAX },
{125,MAX,MAX,MAX,MAX,135,MAX,MAX,MAX,MAX }
int start,
while (true)
if (f == 1)
　　　　　　　//景点信息从文件中读取
ifstream outfile("schooltravel.txt", ios :: out | ios :: binary);
if (!outfile)
cerr && "读取景点介绍文件失败！" &&
string str[max];
int i = 0;
while (getline(outfile, str[i++]));
cout && "|-----------------------景点介绍-------------------| " &&
if (ff == 1)
cout && str[0] &&
else if (ff == 2)
cout && str[1] &&
else if (ff == 3)
cout && str[2] &&
else if(ff == 4)
cout && str[3] &&
else if (ff == 5)
cout && str[4] &&
else if (ff == 6)
cout && str[5] &&
else if (ff == 7)
cout && str[6] &&
else if (ff == 8)
cout && str[7] &&
else if (ff == 9)
cout && str[8] &&
else if (ff == 10)
cout && str[9] &&
cout && "|-------------------------------------------------|" &&
else if (f == 2)
cin && start &&
ShortestPath_DIJ(amg, start - 1);
int temp = end-1;
int temp1, temp2;
int flag[max], m = 0;
cout && "从" && amg.vexs[start - 1] && "到" && amg.vexs[end - 1] && "最短路径为：" ;
while (temp!= -1)
flag[m++] =
temp2 = Path[temp1];
temp = temp2;
for (int i = m-1; i &= 0; i--)
cout &&amg.vexs[flag[i]] && "-&";
cout && "最短路径值为：" && D[end - 1] &&"米"&&
else if (f == 3)
backGround();
else if (f == 4)
cout && "&&&退出成功！" &&
（4）运行截图：
以上就是关于C++用Dijkstra算法(迪杰斯特拉算法)求最短路径的全部内容了，希望本文的内容对大家的学习或者工作带来一定的帮助，如果有疑问大家可以留言交流。
您可能感兴趣的文章:
大家感兴趣的内容
12345678910
最近更新的内容
常用在线小工具