用vb.netl编写的floyd算法求两点间的最短路径,怎么输出path经过的顶点序列?
来源:学生作业帮助网 编辑:六六作业网 时间:2024/08/27 11:30:29
用vb.netl编写的floyd算法求两点间的最短路径,怎么输出path经过的顶点序列?
用vb.netl编写的floyd算法求两点间的最短路径,怎么输出path经过的顶点序列?
用vb.netl编写的floyd算法求两点间的最短路径,怎么输出path经过的顶点序列?
Function Min(x() as integer,y() as integer) as double
dim i,j,k,a
dim m() as double
dim s() as string
dim mins as string
redim m(ubound(x),ubound(x))
redim s(ubound(x),ubound(x))
for i=1 to ubound(x)-1 '从起始点0点到i点的距离
m(i,0)=((x(i)-x(0))^2+(y(i)-y(0))^2)^0.5
s(i,0)="0-" & cstr(i)
next
'从起始点开始经过K个点后到达i点的最短距离m(i,k),s为各点的连线如"0-3-2-1-4"
for k=1 to ubound(x)-2
for i=1 to ubound(x)-1
m(i,k)=10^307
for j=1 to ubound(x)-1
if instr(s(j,k-1),cstr(i))=0 then'避免重复走一点
a=((x(i)-x(j))^2+(y(i)-y(j))^2)^0.5
if a+m(j,k-1)<m(i,k) then
m(i,k)=a+m(j,k-1)
s(i,k)=s(j,k-1) & "-" & cstr(i)
endif
end if
next
next
next
'计算经过各点后到达最后一个点的最短距离
min=10^307
for j=1 to ubound(x)-1
a=((x(ubound(x))-x(j))^2+(y(ubound(x))-y(j))^2)^0.5
if a+m(j,ubound(x)-2)<min then
min=a+m(j,ubound(x)-2)
mins=s(j,ubound(x)-2) & "-" & cstr(ubound(x))
end if
next
msgbox "最短距离:" & min & vbcrlf & "最短路径:" & mins
End function
private sub Command1_Click
dim x(5) as integer
dim y(5) as integer
dim m as double
x(0)=0
y(0)=0
x(1)=40
y(1)=600
.
x(5)=1000
y(5)=1000
m=min(x,y)
End sub