Question

在matlab中怎样求矩阵中任意两点间的距离呢

用矩阵表示一个图形，矩阵中为1的部分表示该两点间有连接，怎样根据矩阵来求任意两点间的最短距离的数量啊？ 例如矩阵为
0 1 0 1 0 0
1 0 1 0 0 0
0 1 0 1 1 1
1 0 1 0 1 0
0 0 1 1 0 1
0 0 1 0 1 0
1到2的距离就为1，点1到3的话就有好几种可能，可以经过2到3，距离为2；经过4到3，距离也为2；或者经过4，5再到3，距离为3。对1到3来说，最短距离为2。以此类推，求出矩阵中任意两点的最短距离并输出。我的数据比较大，是256*256的矩阵。
急求高手们多多指点，不胜感激！50分不成敬意

Answer 1

我们老师给的标准程序，我原封不动送给你吧，系统地讲最短路问题的，要用在你的矩阵的情况的话记得把你里面0全改成inf，耐心看吧，阐述得很完整了，绝对是个高效的算法：

Dijkstra算法
Edser Dijkstra 是荷兰计算机科学家，于1959年发表了Dijkstra算法，时年29岁. 这算法计算具有非负权的N阶矩阵W的图上从源点S（Source）, S(1..N), 出发到达所有各点K, K=1..N, 的最短路。（Edward F. Moore 在1957年也得到类似的算法）.
算法
1. 对每个点I指定一个离点S的距离初始值L(I). 在始点S的值为零, 即L(S)=0，其它点的值为Inf.
2. 所有的点标记为未走访的. 置始点S为当前点C.
3. 对于当前点C, 考虑它的所有未走访的相邻点J, 并更新J的距离值为
L(J)=min(L(J), L(C)+W(C,J))
4. 把当前点C标记为走访过的点. 走访过的点C的距离L(C)就是点S到C的最短距离, 而且以后不再检查走访过得点了.
5. 如果所有的点都是走访过的点, 完成. 不然, 把未走访的点中具有最小距离值的点作为下一个当前点C, 转步骤3.
编制程序的要求: 给定N阶非负权矩阵W, W(I,J)是从点I到点J的距离, W(I,I)的值可以赋以任意值(比较方便的是赋以Inf). 如果只需求源点S(Source)到达指定的终点T(Target)，给出最短路径Z及其长度L(T); 如果不指定终点T时，Z是一个N维行向量，Z(K)表示S点到K点的最短路上K点的前一点, Z(S)=0, L是一个N维行向量, L(K)是S点到K点的最短距离. 如果不给出源点S及终点T, 则默认源点S=1, 按不指定终点的情况办.
MATLAB函数子程序dijkstra.m为:
function [L,Z]=dijkstra(W,S,T)
%用 Dijkstra 算法求最短路,W(I,J)是从点 I 到点 J 的距离, W(I,I)=0,I,J=1..n; 点 I 和点 J 无边直接相连时,W(I,J)=inf.
% L表示从始点 S 到终点 T 的最短距离, Z 表示点 S 到 T 的一条最短路径. 当不给出终点 T 时，L(J)表示从点 S 到点 J 的最短距离, J=1..n; Z(I)表示最短路径上点 I 的前一点(父亲点),
% 可由 Z 追溯最短路径，当不给出起点 S 及终点 T 时默认 S = 1 及按不指定终点的情况办.
if nargin<2 S=1;T=0; elseif nargin<3 T=0; end;%如只给出W, 默认始点 S=1;算出S到所有点的距离; 如没给出终点, 算出S到所有点的距离;
N=length(W(:,1));%顶点数
L=Inf*ones(1,N);,L(S)=0;%L赋初值，在S点为0，其它点为Inf
C=S; %当前点为始点S
Q=1:N;% 未走访的顶点集
Z=S*ones(1,N); Z(S)=0;% Z赋初值,因始点 S 无父亲点,故把 S 点的Z值改为0
for K=1:N % 更新 L 和 Z 的循环
Q=setdiff(Q,C); %当前点 C 未走访的点集
[L(Q),ind]=min([L(Q);L(C)+W(C,Q)]);%当前点C已走访了所有的相邻的未走访的点，更新 L
Z(Q(find(ind==2)))=C; %更新Z, 至此C已是走访过的点了
if T&C==T %若 C 点是终点 T, 不用再计算到其它未走访的点的最短路
L=L(T); %最短路长；
road=T;%最短路径终点；
while T~=S%追溯最短路径上的点
T=Z(T); road=[road,T];
end
Z=road(length(road):-1:1); %颠倒次序；
return;
end;
[null, mC]=min(L(Q));
if null==Inf
disp('到值是Inf的点的路不通！'); Z(find(L==Inf))=nan; return;
else
C=Q(mC);% 把未走访的点集Q中与始点距离最近的点作为新的当前点C;
end;end;
Dijkstra算法的证明：
以下实质上是用动态规划思想的证明.
记第 K 阶段开始时考虑的当前点为C(K），则第 K 阶段完成时确定的当前点为C(K+1)，记集合P(K)={C(1),C(2),…,C(K)}, 记 Q(K)为 P(K) 的余集. 我们来证明对于每个点V∈P(K), L(V)是从源点S到点V点的最短路的长度， K=1..N.
证明：对 K 施行数学归纳法，当 K=1 时， P(1)={S}, V=S, L(V)=0, 命题真; 设对于K=M, M≥1, N≥M时命题真, 即当V∈P(M)时， L(V)是S到V的最短路的长度. 由于P(M+1)=P(M)∪{C(M+1)}, 所以只要证明 L(C(M+1))是点S到C(M+1)点的最短路的长度. 记 R:=C(1)..C(M+1) 是从 S=C(1) 到 C(M+1)的任意一条路， 记L(C(J);I)为在K=I阶段, J>I时更新的L(C(J))的值. 则从 S 出发沿路 R 往 C(M+1)走时, 必存在第一条边(C(I),C(J))使得C(I)∈P(M)，C(J)∈Q(M). 由归纳假设, 这条路 R 的长度W(R)≥L(C(I))+W(C(I),C(J))+W(C(J)..C(M+1))
≥L(C(I))+W(C(I),C(J)).
按算法,在第K=I阶段完成时，L(C(I))+W(C(I),C(J))≥L(C(J);I). 因I≤M, 故L(C(J);I)≥L(C(J);M), 从而W(R)≥L(C(J);M). 由算法, L(C(M+1))≤L(C(J);M); 故W(R)≥L(C(M+1)); 另外按算法, 确有长度等于L(C(M+1))的一条路径, 证毕.

Answer 2

根据lz要求，最合适的是floyd算法
下面就是根据这个算法写的代码，lz可以自己改成函数
D=[0
1
0
1
0
0
1
0
1
0
0
0
0
1
0
1
1
1
1
0
1
0
1
0
0
0
1
1
0
1
0
0
1
0
1
0];
n=length(D);
for
k=1:n
for
i=1:n
for
j=1:n
if
0<D(i,k)
&
0<D(k,j)
if
D(i,j)==0
&
i~=j
D(i,j)=D(i,k)+D(k,j);
else
D(i,j)=min(D(i,j),D(i,k)+D(k,j));
end
end
end
end
end
答案就储存在D矩阵当中，这里
D
=
0
1
2
1
2
3
1
0
1
2
2
2
2
1
0
1
1
1
1
2
1
0
1
2
2
2
1
1
0
1
3
2
1
2
1
0
算法为O(n3)的，256^3=2^24
大概等于1600万
效率上完全能够忍受。

Answer 3

根据lz要求，最合适的是floyd算法

下面就是根据这个算法写的代码，lz可以自己改成函数

D=[0 1 0 1 0 0
1 0 1 0 0 0
0 1 0 1 1 1
1 0 1 0 1 0
0 0 1 1 0 1
0 0 1 0 1 0];

n=length(D);

for k=1:n
for i=1:n
for j=1:n
if 0<D(i,k) & 0<D(k,j)
if D(i,j)==0 & i~=j
D(i,j)=D(i,k)+D(k,j);
else
D(i,j)=min(D(i,j),D(i,k)+D(k,j));
end
end
end
end
end

答案就储存在D矩阵当中，这里
D =
0 1 2 1 2 3
1 0 1 2 2 2
2 1 0 1 1 1
1 2 1 0 1 2
2 2 1 1 0 1
3 2 1 2 1 0

算法为O(n3)的，256^3=2^24 大概等于1600万

效率上完全能够忍受。

Answer 4

你这个题目是图论中的题目，有现成的解决方案，算法名称叫：迪克斯杰德拉算法。那个算法是针对如何搜索最短路径的（不是全局最优）：即查看所有与当前点最近的点，继续向前走，直至目的地。
256*256并不算大，因为你不是每次都找出所有点来计算而是针对当前点找一条通向下一个点的路径，当是你要存储当前点的路径，以应对当走不通时进行回溯！具体算法写要花费大概一到两个小时。

Answer 5

你看看下面这个程序是不是你要的。
http://zhidao.baidu.com/question/150459619.html