数据结构迷宫-学校超市选址、停车场管理算法

1 课课 程程 设设 计计 课课 程 程 数数 据据 结结 构构 课程设计名称 课程设计名称 1 迷宫求解路径问题 2 停车场管理问题停车场管理问题 3 学校超市选址问题学校超市选址问题 专专 业业 班班 级级 学学 生生 姓姓 名名 2 利用栈实现迷宫的求解 一 一 要解决的问题要解决的问题 以一个 m n 的长方阵表示迷宫 0 和 1 分别表示迷宫中的通路和障碍 设计一个程 序 对任意设定的迷宫 求出一条从入口到出口的通路 或得出没有通路的结论 二 算法基本思想描述二 算法基本思想描述 用一个字符类型的二维数组表示迷宫 数组中每个元素取值 0 表示通路 或 1 表 示墙壁 二维数组的第 0 行 第 m 1 行 第 0 列 第 m 1 列元素全置成 1 表示迷宫的 边界 第 1 行第 1 列元素和第 m 行第 n 列元素置成 0 表示迷宫的入口和出口 走迷宫的过程可以模拟为一个搜索的过程 每到一处 总让它按东 南 西 北 4 个方向 顺序试探下一个位置 用二维数组 move 记录 4 个方向上行下标增量和列下标增量 则沿第 i 个方向前进一步 可能到达的新位置坐标可利用 move 数组确定 Px x move i 0 Py y move i 1 如果某方向可以通过 并且不曾到达 则前进一步 在新位置上继续进行搜索 如果 4 个方向都走不通或曾经到达过 则退回一步 在原来的位置上继续试探下一位置 三 设计 三 设计 1 数据结构的设计 1 定义三元数组元素的结构 typedef struct MazeDirect int Dx 行标 int Dy 列标 int direct 走到下一个坐标点的方向 MazeDirect 2 定义链表节点的结构组成 typedef struct LinkNode elemtype data 数据域 struct LinkNode next 指针域 LinkNode 3 定义链栈的头指针 typedef struct LinkNode top 栈的头指针 LinkStack 4 移动数组结构的定义 3 typedef struct int x y x 为行标 y 为列标 Direction increm 2 算法的设计 1 迷宫图的设计 设迷宫为 m 行 n 列 利用 maze m n 来表示一个迷宫 maze i j 0 或 1 其中 0 表示通路 1 表示不通 当从某点向下试探时 中间点有 4 个方向可以试探 见图 而四个角点有 2 个方 向 其它边缘点有 3 个方向 为使问题简单化我们用 maze m 2 n 2 来表示迷宫 而迷宫的四 周的值全部为 1 这样做使问题简单了 每个点的试探方向全部为 4 不用再判断当前点的试 探方向有几个 同时与迷宫周围是墙壁这一实际问题相一致 假设有 6 行 8 列的迷宫 如下图为 maze 8 10 构造的迷宫 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 0 0 1 0 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 1 1 0 1 1 1 1 1 1 0 0 0 1 0 0 0 1 1 0 1 1 0 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 2 试探方向的设计试探方向的设计 在上述表示迷宫的情况下 每个点有 4 个方向去试探 如当前点的坐标 x y 与其相邻的 4 个 点的坐标都可根据与该点的相邻方位而得到 如图 2 所示 因为出口在 m n 因此试探顺 序规定为 从当前位置向前试探的方向为从正东沿顺时针方向进行 为了简化问题 方便的求 出新点的坐标 将从正东开始沿顺时针进行的这 4 个方向 用 0 1 2 3 表示东 南 西 北 的坐标增量放在一个结构数组 move 4 中 在 move 数组中 每个元素有两个域组成 x 横坐标增量 y 纵坐标增量 Move 数组如图 3 所示 move 数组定义如下 typedef struct int x 行 int y 列 item item move 4 4 这样对 move 的设计会很方便地求出从某点 x y 按某一方向 v 0 v 3 到达的新点 i j 的坐标 i x move v x j y move v y 3 栈的设计栈的设计 当到达了某点而无路可走时需返回前一点 再从前一点开始向下一个方向继续试探 因此 压入栈中的不仅是顺序到达的各点的坐标 而且还要有从前一点到达本点的方向 即每走一步 栈中记下的内容为 行 列 来的方向 对于图 1 所示迷宫 依次入栈为 栈中每一组数据是所到达的每点的坐标及从该点沿哪个方向向下走的 对于图 3 迷宫 走 的路线为 1 1 0 2 1 1 2 2 0 3 2 1 3 3 0 3 4 0 下脚标表示方向 当无路可走 则应回溯 对应的操作是出栈 沿下一个方向即方向继续试探 栈中元素是一个由行 列 方向组成的三元组 栈元素的设计如下 typedef struct int x y d 横纵坐标及方向 datatype 栈的定义为 SeqStack s 4 如何防止重复到达某点 以避免发生死循环 一种方法是另外设置一个标志数组 mark m n 它的所有元素都初始化为 0 一旦到达了 某一点 i j 之后 使 mark i j 置 1 下次再试探这个位置时就不能再走了 另一种方法 xy 001 110 20 1 3 10 top 3 4 0 3 3 0 3 2 1 2 2 0 2 1 1 1 1 0 图 3 增量数组 move x y 图 2 与点 x y 相邻的 4 个点及坐标 x y 1 x y 1 x 1 y x 1 y 5 是当到达某点 i j 后使 maze i j 置 1 以便区别未到达过的点 同样也能起到防止走 重复点的目的 此处采用后一方法 算法结束前可恢复原迷宫 四 详细设计 四 详细设计 1 1 算法的设计思想及流程图算法的设计思想及流程图 1 1 主要函数的功能说明 主要函数的功能说明 voidvoid ini stack LinkStackini stack LinkStack 初始化链栈初始化链栈 intint empty Stack LinkStackempty Stack LinkStack 判断是否为空栈判断是否为空栈 voidvoid push Stack LinkStackpush Stack LinkStack elemtype elemtype 入栈入栈 elemtypeelemtype pop Stack LinkStackpop Stack LinkStack 出栈出栈 intint size stack LinkStacksize stack LinkStack 栈的规模大小栈的规模大小 2 2 算法描述算法描述 伪代码描述伪代码描述 迷宫求解算法思想如下 1 栈初始化 2 将入口点坐标及到达该点的方向 设为 1 入栈 3 while 栈不空 栈顶元素 x y d 出栈 求出下一个要试探的方向 d 当遇到死路的时候就出栈 寻找原来点的下一 个方向 while 还有剩余试探方向时 if d 方向可走 则 x y d 入栈 求新点坐标 i j 将新点 i j 切换为当前点 x y if x n 结束 else 重置 d 0 else d 五 源程序清单五 源程序清单 include include int m n typedef struct MazeDirect 6 int Dx int Dy int direct MazeDirect 定义三元数组元素的结构 typedef MazeDirect elemtype typedef struct LinkNode elemtype data struct LinkNode next 定义链表节点的结构组成 LinkNode typedef struct LinkNode top 定义链栈的头指针 LinkStack void ini stack LinkStack stack 初始化链栈 stack top NULL int empty Stack LinkStack stack 判断是否为空栈 if stack top NULL return 0 else return 1 void push Stack LinkStack stack elemtype x 入栈 LinkNode s s LinkNode malloc sizeof LinkNode s data x s next stack top stack top s elemtype pop Stack LinkStack stack 出栈 elemtype x LinkNode p elemtype tmpNull 0 0 0 7 if stack top NULL return tmpNull NULL else x stack top data p stack top stack top p next free p return x int size stack LinkStack stack 栈的规模大小 int i LinkNode Numb i 0 Numb stack top while Numb NULL Numb Numb next i return i int w t maze 100 100 typedef struct int x y x 为行标 y 为列标 Direction increm Direction increm MazeMove 4 0 1 1 0 0 1 1 0 typedef MazeDirect TmpType int Maze path 8 MazeDirect tmp path LinkStack s int x y Px Py d flag 0 ini stack tmp Dx 1 tmp Dy 1 tmp direct 1 push Stack while empty Stack x tmp Dx y tmp Dy d tmp direct 1 遇到死路的时候 回溯 通过出栈完成 while d 4 Px x MazeMove d x Py y MazeMove d y if maze Px Py 0 tmp Dx x tmp Dy y tmp direct d push Stack x Px y Py maze x y 1 标记 防止重复点 if x m printf n 到达迷宫出口 d d x y printf n 经过的节点有 d 个 size stack s while empty Stack printf n d d d path Dx path Dy path direct break else d 0 结束 if else d 结束内部 while 结束外部 while return flag void main 9 printf 请输入迷宫图的行数和列数 输入格式为 i j n scanf d d printf 创建迷宫图 n for w 0 w m 2 w for t 0 ttoptop 0 确保栈不空 然后用个 while 1 确保输入的车辆离开 位置的合法性 如果不和法 显示输入有误 要重新输入 通过 while Enter top room 判断离开车辆的位置 如果是中间位置 就 要再用一个栈前面临时开出来的车 等要开出的车开出后 再把临时栈的车看进 车场内 并要调用 PRINT p room 这个函数计算显示费用 然后还要用 if W head W rear int min 15 Time typedef struct node 定义车辆信息结构体 char num 10 Time reach Time leave CarNode typedef struct NODE CarNode stack MAX 1 int top SeqStackCar typedef struct car CarNode data struct car next QueueNode typedef struct Node QueueNode head QueueNode rear LinkQueueCar void InitStack SeqStackCar int InitQueue LinkQueueCar int Arrival SeqStackCar LinkQueueCar void Leave SeqStackCar SeqStackCar LinkQueueCar void List SeqStackCar LinkQueueCar void processloop int prnmenu void 16 main processloop void processloop int ichoice ch SeqStackCar Enter Temp LinkQueueCar Wait InitStack InitStack InitQueue ichoice prnmenu while ichoice scanf d while ichoice4 printf n 输入错误 请从新输入 scanf d return ichoice 18 自定义函数 void InitStack SeqStackCar s 地址栈的初始化 s top 0 s stack s top NULL int InitQueue LinkQueueCar Q 队列的初始化 Q head QueueNode malloc sizeof QueueNode if Q head NULL Q head next NULL Q rear Q head return 1 else return 1 void PRINT CarNode p int room 车辆收费 int A1 A2 B1 B2 printf n 车辆离开的时间 scanf d d 此时 scanf 函数以 为接受数字结 19 束符 printf n 离开车辆的车牌号为 puts p num printf n 其到达时间为 d d p reach hour p reach min printf n 离开时间为 d d p leave hour p leave min A1 p reach hour A2 p reach min B1 p leave hour B2 p leave min printf n 应交费用为 2 1f 元 B1 A1 60 B2 A2 price free p 车辆的到达登记 int Arrival SeqStackCar Enter LinkQueueCar W CarNode p QueueNode t p CarNode malloc sizeof CarNode flushall printf n 请输入车牌号 例 闽 B1234 gets p num if Enter toptop printf n 车辆在车场第 d 位置 Enter top printf n 车辆到达时间 scanf d d 20 Enter stack Enter top p else printf n 该车须在便道等待 有车位时进入车场 getch t QueueNode malloc sizeof QueueNode t data p t next NULL W rear next t W rear t void Leave SeqStackCar Enter SeqStackCar Temp LinkQueueCar W 车辆的离开 int room CarNode p t QueueNode q if Enter top 0 判断车场是否为空 while 1 printf n 请输入车在车场的位置 1 d Enter top scanf d if room 1 21 else printf n 输入有误 请重输 while Enter top room 把要删除的车辆的前面的车开出来 进临时栈 即 如果是 1 2 号就要用到临时栈 如果 enter top room 也就是三号的话就不必用到临时 栈 Temp top Temp stack Temp top Enter stack Enter top Enter stack Enter top NULL Enter top p Enter stack Enter top 把要删除的车辆节点赋给 p Enter stack Enter top NULL Enter top while Temp top 1 再把临时栈里德车辆进停车场 Enter top Enter stack Enter top Temp stack Temp top Temp stack Temp top NULL Temp top PRINT p room 调用计费函数计费 if W head W rear t q data Enter top printf n 便道的 s 号车进入车场第 d 位置 t num Enter top printf n 请输入 s 号车进入车场的时间 t num 22 scanf d d W head next q next if q W rear W rear W head Enter stack Enter top t free q else printf n 便道里没有车 n else printf n 车场里没有车 void List1 SeqStackCar S 显示车场里的车辆情况 int i if S top 0 printf n 车场 printf n 位置 到达时间 车牌号 n for i 1 itop i printf d i printf d d S stack i reach hour S stack i reach min puts S stack i num else printf n 车场里没有车 23 void List2 LinkQueueCar W 显示便道上的车辆情况 QueueNode p int i p W head next if W head W rear printf n 等待车辆的号码为 for i 1 p NULL i printf n 第 d 车辆 i puts p data num p p next else printf n 便道里没有车 printf n int menu int ichoice system cls printf 查看车辆列表显示 printf n 1 车场列表 n 2 便道列表 n 3 返回主菜单 n printf n 请选择 24 scanf d while ichoice3 printf n 输入错误 请重新输入 scanf d return ichoice void List SeqStackCar S LinkQueueCar W 显示 遍历 int ichoice ichoice menu while ichoicearcs adj 在新图的基础上利用佛洛依德算法求得任意两点之间的最短路径及其相应 在新图的基础上利用佛洛依德算法求得任意两点之间的最短路径及其相应 的路径长度 将其存储在数组名为的路径长度 将其存储在数组名为 A 的数组中 的数组中 然后再求生成树上各点到其 然后再求生成树上各点到其 他点的距离之和 比如 他点的距离之和 比如 A 0 1 A 0 2 A 0 3 A G vexnum G vexnum 然后将求和结果一次存到数组名为然后将求和结果一次存到数组名为 B 的数组中 再对的数组中 再对 B 数组元素进行比较大小 数组元素进行比较大小 求得最小元素 其下标即为最优点存储在定点数组求得最小元素 其下标即为最优点存储在定点数组 vexs 中的序号 中的序号 三 详细设计三 详细设计 1 1 数据结构的设计数据结构的设计 1 1 邻接矩阵数据结构 邻接矩阵数据结构 typedeftypedef structstruct VRTypeVRType adj adj 相通情况相通情况 AdjMatrix MAX VERTEX NUM MAX VERTEX NUM AdjMatrix MAX VERTEX NUM MAX VERTEX NUM 2 2 图的数据结构 图的数据结构 typedeftypedef structstruct VertexTypeVertexType vexs MAX VERTEX NUM vexs MAX VERTEX NUM 顶点向量顶点向量 AdjMatrixAdjMatrix arcs arcs 邻接矩阵邻接矩阵 intint f MAX VERTEX NUM f MAX VERTEX NUM 各单位去超各单位去超 市的频率 市的频率 intint vexnum vexnum 图的当前顶点数图的当前顶点数 arcnum arcnum 图的当前弧数图的当前弧数 MGraph MGraph 3 3 记录从顶点集 记录从顶点集 U U 到到 V UV U 的代价最小的边的辅助数组的数据结构 的代价最小的边的辅助数组的数据结构 typedeftypedef structstruct VertexTypeVertexType adjvex adjvex VRTypeVRType lowcost lowcost minside MAX VERTEX NUM minside MAX VERTEX NUM 2 2 算法的设计思想及流程图算法的设计思想及流程图 1 1 主要函数的功能说明 主要函数的功能说明 31 1 1 若 G 中存在顶点 u 则返回该顶点在图中位置 否则返回 1 int LocateVex MGraph VertexType u 5 2 数组 邻接矩阵 表示法 构造无向网 G int Create MGraph 由于要输入定点名称和权值来建立无向图 所以在此处要调用 locatevex Mgraph VertexType u 找到对应该点名称的存储在数组中的序 号 int Create MGraph 3 or i 0 i G vexnum i for j 0 jarc adj 作为新图 R 各边的权值 然后经由佛洛依德算法得到任意两点之间的最短 路径 存到数组 A 中 2 计算各点分别到所有其他点的路径值之和 即 B 0 B 1 B 2 B G vexnum 3 再显示佛洛依德算法的计算过程 即显示各点到其他点的路径 无穷大 的权值对应的边不显示 4 根据计算出来的 B 数组的数组 选择出最小值 求出其对应下标所对 32 应的顶点名称 即为超市的最佳地址 2 2 模块结构及流程图 模块结构及流程图 开始 Main 输入基本信息 创建图 G 初始化用于记录权值的数组 a 初 始化所有边的权值都为无穷大 GreatMgraph Gh 普利姆算法 求得最小生成树 用数组 a 记录最 小生成树各边的权值 改变原来数组 a 相应的数 值 根据数组 a 创建新图 R 用弗洛伊德算法求得 任意两点之间 的路径 及其最短路径长度 用数组 B 记录各点到其他点的距离之和 比如对于一个有五 个顶点的图 B 0 表示从 0 到 1 2 3 4 点的距离之和 比较数组 B 中元素的大小 最小的那个对应的下标即为最优点 输出对应下标的顶点名称 即为超市的最佳地址 结束 创建图 G 33 3 3 主要模块算法描述 主要模块算法描述 1 1 用普里姆算法从第用普里姆算法从第 u u 个顶点出发构造网个顶点出发构造网 G G 的最小生成树的最小生成树 T T 输输 出出 T T 的各条边的各条边 voidvoid MiniSpanTree PRIM MGraph VertexType int MiniSpanTree PRIM MGraph VertexType int 构造出最小生成树后 利用数组构造出最小生成树后 利用数组 a a 初始值各个元素为无穷大 存 初始值各个元素为无穷大 存 储最小生成树各边的权值 储最小生成树各边的权值 2 2 用佛洛依德算法求带权有向图的最短路径用佛洛依德算法求带权有向图的最短路径 voidvoid Floyed MGraphFloyed MGraph MGraph MGraph 首先先将数组首先先将数组 a a 的各个元素赋给新图的各个元素赋给新图 R R 作为新图 作为新图 R R 各边的权值各边的权值 然后经由然后经由 34 佛洛依德算法得到任意两点之间的最短路径 然后存到数组佛洛依德算法得到任意两点之间的最短路径 然后存到数组 A A 中中 将最小生成树的各点到其他点的距离相加 存到数组将最小生成树的各点到其他点的距离相加 存到数组 B B 中 在通过对数组中 在通过对数组 B B 元素的比较大小 是最小值的那一点即为最优点 因为该点到其他点的元素的比较大小 是最小值的那一点即为最优点 因为该点到其他点的 距离最小距离最小 四 课程设计过程中的关键算法四 课程设计过程中的关键算法 1 佛洛依德算法表述 第一步 让所有路径加上中间顶点 1 取 A i j 与 A i 1 A 1 j 中较 小的值作 A i j 的新值 完成后得到 A 1 如此进行下去 当第 k 步完成后 A k i j 表示从 i 到就且路径上的中间顶点的路径的序号小于或等于 k 的 最短路径长度 当第 n 1 步完成后 得到 A n 1 A n 1 即所求结果 A n 1 i j 表示从 i 到 j 且路径上的中点顶点的序号小于或等于 n 1 的最 短路径长度 即 A n 1 i j 表示从 i 到 j 的最短路径长度 代码如下 代码如下 voidvoid Floyed MGraphFloyed MGraph G MGraph G MGraph R R 带权有向图求带权有向图求 最短路径最短路径 floydfloyd 算法算法 intint A MAX VERTEX NUM MAX VERTEX NUM B MAX VERTEX NUM path MAA MAX VERTEX NUM MAX VERTEX NUM B MAX VERTEX NUM path MA X VERTEX NUM MAX VERTEX NUM X VERTEX NUM MAX VERTEX NUM intint i j k pre min i j k pre min intint count MAX VERTEX NUM count MAX VERTEX NUM for i 0 ivexnum i for i 0 ivexnum i 初始化初始化 A A 和和 path path 数组数组 for j 0 jvexnum j for j 0 jvexnum j 置初值 置初值 35 A i j R arcs i j adj A i j R arcs i j adj path i j 1 path i j 1 count i 0 count i 0 for k 0 kvexnum k for k 0 kvexnum k k k 代表运算步骤代表运算步骤 for i 0 ivexnum i for i 0 ivexnum i for j 0 jvexnum j for j 0 jvexnum j if A i j A i k A k j if A i j A i k A k j 从从 i i 经经 j j 到到 k k 的一条路径更短的一条路径更短 A i j A i k A k j A i j A i k A k j path i j k path i j k 2 2 普里姆算法 普里姆算法 36 voidvoid MiniSpanTree PRIM MGraphMiniSpanTree PRIM MGraph G VertexTypeG VertexType u intu int a MAX VERTEX NUM MAX VERTEX NUM a MAX VERTEX NUM MAX VERTEX NUM intint i j k m i j k m minsideminside closedge closedge k LocateVex G u k LocateVex G u for j 0 j G vexnum j for j 0 j G vexnum j 辅助数组初始化辅助数组初始化 if j k if j k strcpy closedge j adjvex u strcpy closedge j adjvex u 所有边依附的在所有边依附的在 U U 中中 的顶点为的顶点为 u u closedge j lowcost G arcs k j adj closedge j lowcost G arcs k j adj 所有节点所有节点 j j 到节点到节点 k k 的距离的距离 closedge k lowcost 0 closedge k lowcost 0 初始初始 U u U u printf printf 最小代价生成树的各条边为最小代价生成树的各条边为 n n for i 1 i G vexnum i for i 1 i G vexnum i 选择其余选择其余 G vexnum 1G vexnum 1 个顶点个顶点 k minimum closedge G k minimum closedge G 求出求出 T T 的下一个结点 第的下一个结点 第 K K 顶顶 37 点点 printf s s n closedge k adjvex G vexs k printf s s n closedge k adjvex G vexs k 输出生成树的边输出生成树的边 m LocateVex G closedge k adjvex m LocateVex G closedge k adjvex a k m a m k closedge k lowcost a k m a m k closedge k lowcost closedge k lowcost 0 closedge k lowcost 0 第第 K K 顶点并入顶点并入 U U 集集 for j 0 j G vexnum j for j 0 j G vexnum j if G arcs k j adj closedge j lowcost if G arcs k j adj closedge j lowcost 新顶点并入新顶点并入 U U 集后重新选择最小边集后重新选择最小边 strcpy closedge j adjvex G vexs k strcpy closedge j adjvex G vexs k closedge j lowcost G arcs k j adj closedge j lowcost G arcs k j adj 五 源程序清单五 源程序清单 include malloc h include stdlib h include stdio h 38 define MAX VERTEX NUM 20 最大顶点个数最大顶点个数 define MAX NAME 3 顶点字符串的最大长度顶点字符串的最大长度 1 define INFINITY 32767 typedef int VRType typedef char InfoType typedef char VertexType MAX NAME 邻接矩阵的数据结构邻接矩阵的数据结构 typedef struct VRType adj 相通情况相通情况 AdjMatrix MAX VERTEX NUM MAX VERTEX NUM 图的数据结构图的数据结构 typedef struct VertexType vexs MAX VERTEX NUM 顶点向量顶点向量 AdjMatrix arcs 邻接矩阵邻接矩阵 int f MAX VERTEX NUM 各单位去超市的频率 各单位去超市的频率 int vexnum 图的当前顶点数图的当前顶点数 arcnum 图的当前弧数图的当前弧数 MGraph 记录从顶点集记录从顶点集 U 到到 V U 的代价最小的边的辅助数组定义的代价最小的边的辅助数组定义 typedef struct VertexType adjvex VRType lowcost 39 minside MAX VERTEX NUM 若若 G 中存在顶点中存在顶点 u 则返回该顶点在图中位置则返回该顶点在图中位置 否则返回否则返回 1 int LocateVex MGraph G VertexType u int i for i 0 i vexnum fflush stdin printf 请输入请输入 d 个顶点的值个顶点的值 最多包含最多包含vexnum MAX NAME for i 0 ivexnum i 构造顶点向量构造顶点向量 gets G vexs i for i 0 i G vexnum i 初始化邻接矩阵初始化邻接矩阵 for j 0 jvexnum j 40 G arcs i j adj INFINITY 网初始化为无穷大网初始化为无穷大 printf 请输入相通两边的名称和权值请输入相通两边的名称和权值 for k 0 karcs i j adj G arcs j i adj w 无向无向 return 1 void creatext MGraph G int a MAX VERTEX NUM MAX VERTEX NUM MGraph R int i j k for i 0 ivexnum i 初始化邻接矩阵初始化邻接矩阵 for j 0 jvexnum j R arcs i j adj a i j printf 输入所有单位去超市的相对频率输入所有单位去超市的相对频率 输入格式为输入格式为 a b c n for k 0 kvexnum k 41 scanf d for i 0 ivexnum i 以距离和频率之积作以距离和频率之积作 为权值 为权值 for j 0 jvexnum j R arcs i j adj R arcs i j adj R f i 最终最终 权值非完全无向 权值非完全无向 void Floyed MGraph G MGraph R 带权有向图求最短路径带权有向图求最短路径 floyd 算法算法 int A MAX VERTEX NUM MAX VERTEX NUM B MAX VERTEX NUM p ath MAX VERTEX NUM MAX VERTEX NUM int i j k pre min int count MAX VERTEX NUM for i 0 ivexnum i 初始化初始化 A 和和 path 数组数组 for j 0 jvexnum j 置初值 置初值 A i j R arcs i j adj path i j 1 count i 0 for k 0 kvexnum k k 代表运算步骤代表运算步骤 for i 0 ivexnum i 42 for j 0 jvexnum j if A i j A i k A k j 从从 i 经经 k 到到 j 的一条路径更的一条路径更 短短 A i j A i k A k j path i j k for i 0 ivexnum i B i 0 B 数组初始化数组初始化 for i 0 ivexnum i for j 0 jvexnum j if i j B i B i A i j printf Floyed 算法求解如下算法求解如下 n for i 0 ivexnum i for j 0 jvexnum j if i j printf n s s G vexs i G vexs j if A i j INFINITY if i j 43 printf 不存在路径不存在路径 n 可不用 因为如果要选最佳地点 题目所给的应该是连通可不用 因为如果要选最佳地点 题目所给的应该是连通 图图 else printf 路径长度为路径长度为 d n A i j printf 路径为路径为 s G vexs i pre path i j while pre 1 printf s G vexs pre pre path pre j printf s G vexs j printf n s 到其他地点的路径总和为 到其他地点的路径总和为 d G vexs i B i min B 0 k 0 for i 0 ivexnum i if B i vexs k 44 求求 closedge lowcost 的最小正值的最小正值 int minimum minside SZ MGraph G int i 0 j k min while SZ i lowcost i min SZ i lowcost 第一个不为第一个不为 0 的值的值 k i for j i 1 j0 if min SZ j lowcost min SZ j lowcost k j return k 用普里姆算法从第用