最短路径旅行问题

短距离旅游

具有欧拉回路的图称为欧拉图（EulerGraph）,具有欧拉通路而无欧拉回路的图称为半欧拉图,通过图中所有边一次且仅一次行遍所有顶点的回路称为欧拉回路,通过图（无向图或有向图）中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路。

和哈密顿回路相比,哈密顿回路是所有点仅仅经历一次。

从北京（Pe）乘飞机到东京(T)、纽约(N)、墨西哥城(M)、伦敦(L)、巴黎(Pa)。

各城市之,每城市恰去一次再回北京,五城市做旅游,使旅程最短,应如何安排旅游线。

间的航线距离如表7

表7 六城市间的距离。

L M N Pa Pe T。

L 56 35 21 51 60。

M 56 21 57 78 70。

N 35 21 36 68 68。

Pa 21 57 36 51 61。

Pe 51 78 68 51 13。

T 60 70 68 61 13。

则可编写程序：

main.m

clc,clear

global a

a=zeros(6);。

a(1,2)=56;a(1,3)=35;a(1,4)=21;a(1,5)=51;a(1,6)=60;。

a(2,3)=21;a(2,4)=57;a(2,5)=78;a(2,6)=70;。

a(3,4)=36;a(3,5)=68;a(3,6)=68; a(4,5)=51;a(4,6)=61;。

a(5,6)=13; a=a+a'; L=size(a,1);。

c1=[5 1:4 6];%起点是5然后按照顺序是第一个初始圈。

[circle,long]=modifycircle(c1,L);。

c2=[5 6 1:4];%改变初始圈,该算法的最后一个顶点不动。

[circle2,long2]=modifycircle(c2,L);。

if long2

circle;long;。

子函数modifycircle.m。

function [circle,long]=modifycircle(c1,L)。

global a

flag=1;

while flag>0。

flag=0;

for m=1:L-3。

for n=m+2:L-1。

if a(c1(m),c1(n))+a(c1(m+1),c1(n+1))。

circle=c1;。

结果：