学帮网这是一个图论的问题图是一个加权有向图,我已经算出各个顶点之间的最短距离就是根据这个加权有向图来选择3个地点作为自来水厂的位置算法：第一步：从28个地点中 任选3个点 来作为自来
来源：学生作业学帮网 编辑：学帮网 时间：2024/05/31 06:33:20
这是一个图论的问题
图是一个加权有向图,我已经算出各个顶点之间的最短距离
就是根据这个加权有向图来选择3个地点作为自来水厂的位置
算法：
第一步：从28个地点中 任选3个点 来作为自来水厂的选址位置
第二步：除去选中的3个点,遍历剩下的25个点,求出每个地点到三个选址地点的最短距离,然后再求出这25个点到最近自来水厂的最短距离之和,使最短距离之和最小
怎样用Lingo编程来实现这个算法
火急
Dijkstra算法是很有代表性的最短路算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等
注意：你的指定点开始的问题,直接从把下面的东西看完后,应用（6）就可以解决,任意开始点的话,就把所有点都指定一下就行了.
再补充一个,这个算法一般图论书上都有,但是写的非常之高深莫测,看不懂的.建议去看清华大学的数据结构与算法这本书上的算法,（蓝色封皮的）
设S为最短距离已确定的顶点集（看作红点集）,V-S是最短距离尚未确定的顶点集（看作蓝点集）.
①初始化
初始化时,只有源点s的最短距离是已知的(SD(s)=0),故红点集S={s},蓝点集为空.
②重复以下工作,按路径长度递增次序产生各顶点最短路径
在当前蓝点集中选择一个最短距离最小的蓝点来扩充红点集,以保证算法按路径长度递增的次序产生各顶点的最短路径.
当蓝点集中仅剩下最短距离为∞的蓝点,或者所有蓝点已扩充到红点集时,s到所有顶点的最短路径就求出来了.
注意：
①若从源点到蓝点的路径不存在,则可假设该蓝点的最短路径是一条长度为无穷大的虚拟路径.
②从源点s到终点v的最短路径简称为v的最短路径；s到v的最短路径长度简称为v的最短距离,并记为SD(v).
（3）在蓝点集中选择一个最短距离最小的蓝点k来扩充红点集
根据按长度递增序产生最短路径的思想,当前最短距离最小的蓝点k的最短路径是：
源点,红点1,红点2,…,红点n,蓝点k
距离为：源点到红点n最短距离+边长
为求解方便,设置一个向量D[0．．n-1],对于每个蓝点v∈ V-S,用D[v]记录从源点s到达v且除v外中间不经过任何蓝点(若有中间点,则必为红点)的"最短"路径长度（简称估计距离）.
若k是蓝点集中估计距离最小的顶点,则k的估计距离就是最短距离,即若D[k]=min{D[i] i∈V-S},则D[k]=SD(k).
初始时,每个蓝点v的D[c]值应为权w,且从s到v的路径上没有中间点,因为该路径仅含一条边.
注意：
在蓝点集中选择一个最短距离最小的蓝点k来扩充红点集是Dijkstra算法的关键
（4）k扩充红点集s后,蓝点集估计距离的修改
将k扩充到红点后,剩余蓝点集的估计距离可能由于增加了新红点k而减小,此时必须调整相应蓝点的估计距离.
对于任意的蓝点j,若k由蓝变红后使D[j]变小,则必定是由于存在一条从s到j且包含新红点k的更短路径：P=.且D[j]减小的新路径P只可能是由于路径和边组成.
所以,当length(P)=D[k]+w小于D[j]时,应该用P的长度来修改D[j]的值.
（5）Dijkstra算法
Dijkstra(G,D,s){
//用Dijkstra算法求有向网G的源点s到各顶点的最短路径长度
//以下是初始化操作
S={s}；D[s]=0； //设置初始的红点集及最短距离
for( all i∈ V-S )do //对蓝点集中每个顶点i
D[i]=G[s][i]； //设置i初始的估计距离为w
//以下是扩充红点集
for(i=0;iD[k]+G[k][j])
//新红点k使原D[j]值变小时,用新路径的长度修改D[j],
//使j离s更近.
D[j]=D[k]+G[k][j]；
}
}
（6）保存最短路径的Dijkstra算法
设置记录顶点双亲的向量P[0．．n-1]保存最短路径：
当顶点i无双亲时,令P[i]=-1.
当算法结束时,可从任一P[i]反复上溯至根(源点)求得顶点i的最短路径,只不过路径方向正好与从s到i的路径相反.
.
Dijkstra算法的时间复杂度为O(n2)
参考资料：http://student.zjzk.cn/course_ware/data_structure/web/tu/tu7.5.2.htm