8 Star 20 Fork 3

何群山 / CommunicationNetworks-RouteSelection

加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
克隆/下载
贡献代码
同步代码
取消
提示: 由于 Git 不支持空文件夾,创建文件夹后会生成空的 .keep 文件
Loading...
README
Apache-2.0

CommunicationNetworks-RouteSelection

文件功能介绍

代码文件 功能
workspace.m 代码一步执行工作区
Dijkstra.m Dijkstra算法计算最短路径的距离dist和路径fullPath以及置定节点集Gp
Floyd.m Floyd算法获得完全优化后的权值矩阵W和路由矩阵R
getGraph.m 获取网络图(默认图或者手动输入)
getFloydMinPath 利用Floyd计算得到的W和R获取任意起点v到其他节点的最短路径fullPath及距离dist
drawPath 利用fullPath、dist、point(随机值获取)、figureIndex(图的句柄),绘制对应的最短路径
drawDijkstraPath.m 绘制Dijkstra各轮下对应的最短路径

代码执行效果展示

Dijkstra执行效果图,可看到每一轮更新之后的最短路径情况
图0.1 Dijkstra执行效果图
Floyd执行效果图,可看到执行起点v到其他各节点的最短路径
图0.2 Floyd执行效果图

1.Dijkstra算法求图的单源最短路径

算法思想简述如下: 将图中各点分为两个集合:置定结点集合Gp(并入了最短路径的)、非置定结点集合Gs. 使用dist记录源点v到各点的距离,fullPath记录源点v到其余各点的最短路径.

  1. 将源点v加入置定结点集合Gp
  2. 找出置定结点集合Gp到Gs的当前最短边(及其对应顶点k)
  3. 将该顶点k加入到置定结点集合Gp中,利用k作为中间结点,如果Gp中(i->k+k->j)<(i->j),则更新Gp到Gs的路径,并将中间结点k记录到对应dist中
  4. 循环运行n-1次,将所有剩余结点加入到Gp中

Dijkstra fullPath的更新逻辑

  1. fullPath记录的是源点v到各顶点的最短路径(起点->中间结点s->终点)
  2. 当新的顶点k加入到Gp后,需要利用k作为中间结点更新Gp到Gs的路径,若此时有结点i,j(i属于Gp,j属于Gs),满足(i->k+k->j)<(i->j),则认定源点到j点需要经过中间结点k
  3. 将k结点的当前fullPath对应最短路径,赋值给j的fullPath对应最短路径(记录下来到中间结点k的前面的路径)。
  4. 在j的最短路径后面加上当前的结点号j(终点记录)。

DIjkstra算法流程图

Dijkstra算法流程图
图1.0 Dijkstra算法流程图

图示Dijkstra算法过程

例题图参考《通信网理论与应用》,石文寿主编;Page37页
图1.1 Dijkstra轮数0
初始化Dijkstra图,标出起点V1(置定节点集Gp此时只有V1),及置定节点集Gp与非置定节点集的连线(橙色线. V1-V2,V1-V3,V1-V4)
图1.2 Dijkstra轮数1
选取置定节点集Gp与非置定节点集的连线(橙色线)中最短的那条线(V1-V4),将V4并入置定节点集(节点V4及其连线V1-V4标蓝),同时更新置定节点集Gp与非置定节点集的连线(橙色线. V4-V2,V4-V3,V4-V5)
图1.3 Dijkstra轮数2
选取最短的那条线(V4-V5),将V5并入置定节点集(节点V5及其连线V4-V5标蓝),同时更新置定节点集Gp与非置定节点集的连线(橙色线.V5-V3,V5-V6)
图1.4 Dijkstra轮数3
选取最短的那条线(V5-V3),将V3并入置定节点集(节点V3及其连线V5-V3标蓝),同时更新置定节点集Gp与非置定节点集的连线(橙色线.V3-V2,V3-V6),移除置定节点集本身间的连线(V1-V3.V4-V3)
图1.5 Dijkstra轮数4
选取最短的那条线(V1-V2),将V2并入置定节点集(节点V2及其连线V1-V2标蓝)
图1.6 Dijkstra轮数5
选取最短的那条线(V5-V6),将V6并入置定节点集(节点V6及其连线V5-V6标蓝),此时置定节点集包含所有节点,Dijkstra构造完成最短路径
图1.7 Dijkstra结果图
Dijkstra构造完成的最短路径结果图

2.Floyd算法实现图的任意两点间最短路径

算法思想简述如下: 如果要让任意两点(例如从顶点a点到顶点b)之间的路程变短,只能引入第三个点(顶点k),并通过这个顶点k中转,即a->k->b,才可能缩短原来从顶点a点到顶点b的路程。 图的权值矩阵W(Weight,记录一点到任意各点的最短距离)、最短路由矩阵R(Router,记录中间结点路由) 首先以第一个顶点(k=1:n)作为第一个中间结点, 遍历权值矩阵(i=1:n,j=1:n)来寻找是否能利用当前结点k=1为中间结点,使得w(i->k+k->j)<w(i->j),若满足,则更新(i->j)的距离W(i,j)=w(i->k+k->j),同时更新中间结点路由R(i,j)=k; 利用k=1:n所有结点作为中间结点进行W和R的优化后,最终得到的W和R即为最短路径W和最短路径路由矩阵R.

Floyd算法流程图

Floyd算法流程图
图2.0 Floyd流程图

Floyd fullPath的更新逻辑(非递归算法)

  1. 由于Floyd算法的关键就是利用中间结点优化源点v到终点u的路径
  2. 当找到一个可优化的中间结点k时,将k插入到源点v和终点u中间(v->k(中间结点)->u)
  3. 这时候,需要注意到,v->k可能有中间结点可以优化,k->u也可能有中间结点可以优化,我们需要做这两件事情:1.不断找中间结点插入到路径;2.保证各段没有中间结点可以再优化了
  4. 怎样保证能把所有中间结点都记录下来呢?没有中间结点可优化的条件(R(path(index),path(index+1))==path(index+1))
  5. 设立一个index记录之前已经完成了最优化,一个rNum记录中间结点的个数(便于插入新中间结点),不断寻找index到index+1顶点的中间结点并插入到index到index+1顶点中间,知道index到index+1之间没有中间结点(R(index,index+1)==index+1),这时候令index加一,去更新下一级的index到index+1的中间结点,由此不断优化,不断向前推index,最终当所有的路径都已经没有中间结点可以增加时path(index+1)==u,则表示最优化达到了终点,完成了路径检索。
Apache License Version 2.0, January 2004 http://www.apache.org/licenses/ TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION 1. Definitions. "License" shall mean the terms and conditions for use, reproduction, and distribution as defined by Sections 1 through 9 of this document. "Licensor" shall mean the copyright owner or entity authorized by the copyright owner that is granting the License. "Legal Entity" shall mean the union of the acting entity and all other entities that control, are controlled by, or are under common control with that entity. For the purposes of this definition, "control" means (i) the power, direct or indirect, to cause the direction or management of such entity, whether by contract or otherwise, or (ii) ownership of fifty percent (50%) or more of the outstanding shares, or (iii) beneficial ownership of such entity. "You" (or "Your") shall mean an individual or Legal Entity exercising permissions granted by this License. "Source" form shall mean the preferred form for making modifications, including but not limited to software source code, documentation source, and configuration files. "Object" form shall mean any form resulting from mechanical transformation or translation of a Source form, including but not limited to compiled object code, generated documentation, and conversions to other media types. "Work" shall mean the work of authorship, whether in Source or Object form, made available under the License, as indicated by a copyright notice that is included in or attached to the work (an example is provided in the Appendix below). "Derivative Works" shall mean any work, whether in Source or Object form, that is based on (or derived from) the Work and for which the editorial revisions, annotations, elaborations, or other modifications represent, as a whole, an original work of authorship. For the purposes of this License, Derivative Works shall not include works that remain separable from, or merely link (or bind by name) to the interfaces of, the Work and Derivative Works thereof. "Contribution" shall mean any work of authorship, including the original version of the Work and any modifications or additions to that Work or Derivative Works thereof, that is intentionally submitted to Licensor for inclusion in the Work by the copyright owner or by an individual or Legal Entity authorized to submit on behalf of the copyright owner. For the purposes of this definition, "submitted" means any form of electronic, verbal, or written communication sent to the Licensor or its representatives, including but not limited to communication on electronic mailing lists, source code control systems, and issue tracking systems that are managed by, or on behalf of, the Licensor for the purpose of discussing and improving the Work, but excluding communication that is conspicuously marked or otherwise designated in writing by the copyright owner as "Not a Contribution." "Contributor" shall mean Licensor and any individual or Legal Entity on behalf of whom a Contribution has been received by Licensor and subsequently incorporated within the Work. 2. Grant of Copyright License. Subject to the terms and conditions of this License, each Contributor hereby grants to You a perpetual, worldwide, non-exclusive, no-charge, royalty-free, irrevocable copyright license to reproduce, prepare Derivative Works of, publicly display, publicly perform, sublicense, and distribute the Work and such Derivative Works in Source or Object form. 3. Grant of Patent License. Subject to the terms and conditions of this License, each Contributor hereby grants to You a perpetual, worldwide, non-exclusive, no-charge, royalty-free, irrevocable (except as stated in this section) patent license to make, have made, use, offer to sell, sell, import, and otherwise transfer the Work, where such license applies only to those patent claims licensable by such Contributor that are necessarily infringed by their Contribution(s) alone or by combination of their Contribution(s) with the Work to which such Contribution(s) was submitted. If You institute patent litigation against any entity (including a cross-claim or counterclaim in a lawsuit) alleging that the Work or a Contribution incorporated within the Work constitutes direct or contributory patent infringement, then any patent licenses granted to You under this License for that Work shall terminate as of the date such litigation is filed. 4. Redistribution. You may reproduce and distribute copies of the Work or Derivative Works thereof in any medium, with or without modifications, and in Source or Object form, provided that You meet the following conditions: (a) You must give any other recipients of the Work or Derivative Works a copy of this License; and (b) You must cause any modified files to carry prominent notices stating that You changed the files; and (c) You must retain, in the Source form of any Derivative Works that You distribute, all copyright, patent, trademark, and attribution notices from the Source form of the Work, excluding those notices that do not pertain to any part of the Derivative Works; and (d) If the Work includes a "NOTICE" text file as part of its distribution, then any Derivative Works that You distribute must include a readable copy of the attribution notices contained within such NOTICE file, excluding those notices that do not pertain to any part of the Derivative Works, in at least one of the following places: within a NOTICE text file distributed as part of the Derivative Works; within the Source form or documentation, if provided along with the Derivative Works; or, within a display generated by the Derivative Works, if and wherever such third-party notices normally appear. The contents of the NOTICE file are for informational purposes only and do not modify the License. You may add Your own attribution notices within Derivative Works that You distribute, alongside or as an addendum to the NOTICE text from the Work, provided that such additional attribution notices cannot be construed as modifying the License. You may add Your own copyright statement to Your modifications and may provide additional or different license terms and conditions for use, reproduction, or distribution of Your modifications, or for any such Derivative Works as a whole, provided Your use, reproduction, and distribution of the Work otherwise complies with the conditions stated in this License. 5. Submission of Contributions. Unless You explicitly state otherwise, any Contribution intentionally submitted for inclusion in the Work by You to the Licensor shall be under the terms and conditions of this License, without any additional terms or conditions. Notwithstanding the above, nothing herein shall supersede or modify the terms of any separate license agreement you may have executed with Licensor regarding such Contributions. 6. Trademarks. This License does not grant permission to use the trade names, trademarks, service marks, or product names of the Licensor, except as required for reasonable and customary use in describing the origin of the Work and reproducing the content of the NOTICE file. 7. Disclaimer of Warranty. Unless required by applicable law or agreed to in writing, Licensor provides the Work (and each Contributor provides its Contributions) on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied, including, without limitation, any warranties or conditions of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A PARTICULAR PURPOSE. You are solely responsible for determining the appropriateness of using or redistributing the Work and assume any risks associated with Your exercise of permissions under this License. 8. Limitation of Liability. In no event and under no legal theory, whether in tort (including negligence), contract, or otherwise, unless required by applicable law (such as deliberate and grossly negligent acts) or agreed to in writing, shall any Contributor be liable to You for damages, including any direct, indirect, special, incidental, or consequential damages of any character arising as a result of this License or out of the use or inability to use the Work (including but not limited to damages for loss of goodwill, work stoppage, computer failure or malfunction, or any and all other commercial damages or losses), even if such Contributor has been advised of the possibility of such damages. 9. Accepting Warranty or Additional Liability. While redistributing the Work or Derivative Works thereof, You may choose to offer, and charge a fee for, acceptance of support, warranty, indemnity, or other liability obligations and/or rights consistent with this License. However, in accepting such obligations, You may act only on Your own behalf and on Your sole responsibility, not on behalf of any other Contributor, and only if You agree to indemnify, defend, and hold each Contributor harmless for any liability incurred by, or claims asserted against, such Contributor by reason of your accepting any such warranty or additional liability. END OF TERMS AND CONDITIONS APPENDIX: How to apply the Apache License to your work. To apply the Apache License to your work, attach the following boilerplate notice, with the fields enclosed by brackets "[]" replaced with your own identifying information. (Don't include the brackets!) The text should be enclosed in the appropriate comment syntax for the file format. We also recommend that a file or class name and description of purpose be included on the same "printed page" as the copyright notice for easier identification within third-party archives. Copyright [yyyy] [name of copyright owner] Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

简介

通信与网络路径规划,D算法及F算法MATLAB实现。 展开 收起
Matlab
Apache-2.0
取消

发行版

暂无发行版

贡献者

全部

近期动态

加载更多
不能加载更多了
Matlab
1
https://gitee.com/qunshanhe/communication-networks.git
git@gitee.com:qunshanhe/communication-networks.git
qunshanhe
communication-networks
CommunicationNetworks-RouteSelection
master

搜索帮助