『壹』 图论中求任意两点之间的最短路径用lingo怎么实现，求lingo源程序
请参考：（10个点的最短路径），源顶点编号为10，
!最短路问题;
model:
data:
n=10;
enddata
sets:
cities/1..n/: F; !10个城市;
roads(cities,cities)/
1,2 1,3
2,4 2,5 2,6
3,4 3,5 3,6
4,7 4,8
5,7 5,8 5,9
6,8 6,9
7,10
8,10
9,10
/: D, P;
endsets
data:
D=
6 5
3 6 9
7 5 11
9 1
8 7 5
4 10
5
7
9;
enddata
F(n)=0;
@for(cities(i) | i #lt# n:
F(i)=@min(roads(i,j): D(i,j)+F(j));
);
!显然，如果P(i,j)=1,则点i到点n的最短路径的第一步是i --> j，否则就不是。
由此，我们就可方便的确定出最短路径;
@for(roads(i,j):
P(i,j)=@if(F(i) #eq# D(i,j)+F(j),1,0)
);
end
结果是，
F( 1) 17.00000
F( 2) 11.00000
F( 3) 15.00000
F( 4) 8.000000
F( 5) 13.00000
F( 6) 11.00000
F( 7) 5.000000
F( 8) 7.000000
F( 9) 9.000000
F( 10) 0.000000
『贰』 最短路径 - Dijkstra算法
算法每次都查找距离起始点最近的点，那么剩下的点距离起始点的距离一定比当前点大。
1.选定A节点并初始化，如上述步骤3所示
2.执行上述 4、5两步骤，找出U集合中路径最短的节点D 加入S集合，并根据条件 if ( 'D 到 B,C,E 的距离' + 'AD 距离' < 'A 到 B,C,E 的距离' ) 来更新U集合
3.这时候 A->B, A->C 都为3，没关系。其实这时候他俩都是最短距离，如果从算法逻辑来讲的话，会先取到B点。而这个时候 if 条件变成了 if ( 'B 到 C,E 的距离' + 'AB 距离' < 'A 到 C,E 的距离' ) ，如图所示这时候A->B距离 其实为 A->D->B
思路就是这样，往后就是大同小异了
算法结束
（图片来源于网络）
Dijkstra算法保证能找到一条从初始点到目标点的最短路径，只要所有的边都有一个非负的代价值。在上图中，粉红色的结点是初始结点，蓝色的是目标点，而类菱形的有色区域则是Dijkstra算法扫描过的区域。颜色最淡的区域是那些离初始点最远的，因而形成探测过程（exploration）的边境（frontier）。因而Dijkstra算法可以找到一条最短的路径，但是效率上并不高。
数据结构--Dijkstra算法最清楚的讲解
『叁』 matlab求最短路，运行dijkstra函数
在使用Matlab求解最短路径问题时，可以借助Dijkstra算法。首先，打开Matlab环境，运行或直接按Win+R键，输入notepad，将以下代码复制进去：
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function [d,DD]=dijkstra(D,s) % Dijkstra最短路算法Matlab程序用于求从起始点s到其它各点的最短路 % D为赋权邻接矩阵 % d为s到其它各点最短路径的长度; % DD记载了最短路径生成树 [m,n]=size(D); d=inf.*ones(1,m); d(1,s)=0; dd=zeros(1,m); dd(1,s)=1; y=s; DD=zeros(m,m); DD(y,y)=1; counter=1; while length(find(dd==1))
接着，将该文件保存为dijkstra.m，保存路径最好选择Matlab的工作路径。此文件保存后，即可在Matlab中调用dijkstra函数来计算最短路径。在实际应用中，输入的D矩阵应为赋权邻接矩阵，表示图中各节点之间的连接关系和权重。通过运行dijkstra函数，可以得到从起始点s到其他所有节点的最短路径长度和最短路径生成树。
在编写dijkstra.m文件时，需要注意以下几点：
1. D矩阵的构建。根据实际问题，构建赋权邻接矩阵D。矩阵中的元素D(i,j)表示从节点i到节点j的边权值，若无直接连接，则设为无穷大。
2. 起始点s的选择。确定起始节点s，作为求解最短路径的起点。
3. 算法执行流程。通过while循环不断更新最短路径，直到找到所有节点的最短路径。
通过合理设置D矩阵和起始点s，可以有效地利用Dijkstra算法求解复杂的最短路径问题。值得注意的是，Dijkstra算法适用于无负权边的情况，因此在实际应用中需确保输入数据的正确性。
在应用过程中，可以结合具体问题，对dijkstra函数进行适当修改和扩展，以适应不同的需求。同时，Matlab提供了丰富的绘图功能，可以在求得最短路径后，绘制出路径图，直观地展示最短路径的走向。
总之，通过编写和使用dijkstra.m文件，可以方便地在Matlab中求解最短路径问题，为实际应用提供了有力的支持。