文档介绍：-
. z.
最优路径规划算法设计
问题概述
兵力机动模型的功能是支持实施机动的实体按照指定路线，由作战空间的一点向另外一点的位置移动，并带入实体在移动过程中发生变化的状态信息。
矩阵，即，，也就是说，如果两节点之间有一条弧，那么邻接矩阵中对应元素为1，否那么为0.
图〔a〕和图〔b〕的邻接表矩阵即为
在计算机中用二维数组表示，两节点之间有弧相应的元素为1.
必须指出的是：目前为止，一切最短路算法都只对不含负有向圈的网络有效。实际上，对于含负有向圈的网络，其最短路问题是NP-hard。因此，除非特别说明，一律假定网络不包含负有向圈。此外在实际问题中也会遇到无向网络上的最短路问题，这时原问题一般可以转化为有向网络中上的最短路问题。如果所有弧上的权全为非负数，只需将无向图的一条边代之以两条对称的有向弧即可。如果弧上的权
-
. z.
有负有正，一般来说问题要复杂得多，要具体问题具体分析。本文中所要解决的问题都取权值为正，无向图皆采取两条对称的有向弧问题。
，其中，与关联，称是图的一条道路，为路长，顶点和分别称为的起点和终点，而称为他的部顶点。
假设道路的边互不一样，那么称为迹。假设道路的顶点互不一样，那么称为轨。
称一条道路是闭的，如果它有正的长且起点和终点一样。起点和终点重合的轨叫做圈(cycle)。
假设图G 的两个顶点u, v间存在道路，那么称u和v连通(connected)。u, v间的最短轨的长叫做u, v间的距离。记作d(u,v)。假设图G 的任二顶点均连通，那么称G 是连通图。
显然有：
(i)图P 是一条轨的充要条件是P 是连通的，且有两个一度的顶点，其余顶点的度为2；
(ii)图C 是一个圈的充要条件是C 是各顶点的度均为2 的连通图
应用
以行军途中各目标为图G 的顶点，两目标之间的连线为图G 相应两顶点间的边，得图G 。对G 的每一边e，赋以一个实数w(e)—两目标之间的距离长度，称为e的权，得到赋权图G 。G 的子图的权是指子图的各边的权和。问题就是求赋权图G 中指定的两个顶点间的具最小权的轨。这条轨叫做间的最短路，它的权叫做间的距离，亦记作。
-
. z.
算法设计
Dijkstra算法
定义预览：
Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，注意该算法要求图中不存在负权边。
算法描述
算法思想：
设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合〔用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将参加到集合S中，直到全部顶点都参加到S中，算法就完毕了〕，第二组为其余未确定最短路径的顶点集合〔用U表示〕，按最短路径长度的递增次序依次把第二组的顶点参加S中。在参加的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。
2〕算法步骤：
-
. z.
，S只包含源点，即S＝{v}，v的距离为0。U包含除v外的其他顶点，即:U={其余顶点}，假设v与U中顶点u有边，那么<u,v>正常有权值，假设u不是v的出边邻接点，那么<u,v>权值为∞。
，把k参加S中〔该选定的距离就是v到k的最短路径长度〕。
，修改U中各顶点的距离；假设从源点v到顶点u的距离〔经过顶点k〕比原来距离〔不经过顶点k〕短，那么修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。
。
3〕算法实例
图1是5个节点的赋权无向图
图1 各节点之间的赋权无向图
1
10 100
2 30
5
5