文档介绍：:问题1:将一批货物从甲地运送到乙地,可以经过多条路线,如何求取运费成本最低的线路?问题2:当地下煤气管道改装时,若关闭某个阀门,需要确定受影响的所有用户?问题3:某市拟建立一个消防站,如何确定10分钟之内能到达的所有街道?问题4:常乐村15号在什么地方?——网络分析之最佳路径分析——网络分析之连通分析——网络分析之资源分配————接受或分配资源位置代表地物:可能属性:结点——网络的汇合点代表地物:可能属性:结点——网络的汇合点代表地物:交叉路口、河流汇合点可能属性:结点——网络的汇合点代表地物:交叉路口、河流汇合点可能属性:阻碍强度、资源需求量特殊类型:障碍、拐点链——各种线路代表地物:公路、铁路、煤气管、河流等可能属性:阻碍强度、资源需求量中心——接受或分配资源位置代表地物:水库、商业中心、电站可能属性:中心——接受或分配资源位置代表地物:水库、商业中心、电站可能属性:阻碍强度、资源容量站点——资源增减的点代表地物:车站、库房——可能属性:阻碍强度,(设施服务范围、资源分配范围确定问题)(1)路径分析A、最佳路径分析B、最佳游历方案FS0BCDEG21321421求货物从S0到F最短路径71061069510137ADECB中国邮递员问题答案:ACDEBA解决方案:目前只有近似解法,如启发式搜索、最优插入法等。答案:S0-C-B-D-F或S0-B-D-F解决方案:Dijkstra算法等(下页)Dijkstra最短路径算法描述开始把S放入Open表,令g(s)=0Open表为空表把第一个节点n从Open移至Close表n为目标节点?若子节点ni在close表,取消扩展,否则按公式g(s,ni)=g(s,n)+C(n,ni)计算ni代价:若ni在open表中,且比表中代价小,更改Open表ni代价,父节点修改为n;(S,B)=g(S,A)+C(A,B)Dijkstra最短路径算法描述FS0BCDEG21321421初始化OPEN表和CLOSE表OPEN表路径父节点编码节点号变量n0CLOSE表路径父节点编码节点号编号S0000S000在OPEN表中放置初始节点S0,g(S0)=0设n=0。S0是目标节点?NoOPEN表为空?No将OPEN表中最小路径代价的节点S0放入CLOSE中,编号为n。现扩展刚移入CLOSE表的节点S0S0有两个后继节点,可以扩展扩展S0子节点C,C未在OPEN和CLOSE表中,向OPEN中增加,父节点编码为n,路径为1C01扩展S0子节点B,B未在OPEN和CLOSE表中,向OPEN中增加,父节点编码为n,路径为2B02扩展S0完毕,n=n+1。1将OPEN表中最小路径代价的节点C放入CLOSE中,编号为n。有三个后继节点,可以扩展扩展C子节点S0,S0在CLOSE表中,取消扩展扩展C子节点B,B在OPEN表中,但当前路径2不小于OPEN表中B的路径,取消扩展扩展C子节点E,E未在OPEN和CLOSE表中,向OPEN中增加,父节点编码为n,路径为3E13扩展C完毕,n=n+1。2将OPEN表中最小路径代价的节点B放入CLOSE中,编号为n。31E2B02现扩展刚移入CLOSE表的节点B扩展B子节点S0,S0在CLOSE表中,取消扩展扩展B子节点C,C在CLOSE表中,取消扩展扩展B子节点D,D未在OPEN和CLOSE表中,向OPEN中增加,父节点编码为n,路径为5D25扩展B完毕,n=n+1。3将OPEN表中最小路径代价的节点E放入CLOSE中,编号为n。52D3E13G35F37453G73F4D25F46564F5G3566F46S0CBEDG现扩展刚移入CLOSE表的节点E扩展E子节点C,C在CLOSE表中,取消扩展扩展E子节点G,G未在OPEN和CLOSE表中,向OPEN中增加,父节点编码为n,路径为5扩展E子节点F,F未在OPEN和CLOSE表中,向OPEN中增加,父节点编码为n,路径为7注意,此时虽然已经找到目标节点,但并未找到他的最短路径,需要继续扩展E完毕,n=n+1。将OPEN表中最小路径代价的节