不确定图中的最短路径树算法研究

摘要

在通信网络中，组播是一种重要的通信方式，是一种一对多的连接类型的通信方式。随着网络技术的发展，组播在分布式系统、视频点等多媒体业务中得到广泛的应用。实现组播的关键是选择合理的组播算法构造一颗组播树。我们使用一个带权的无向图来表示通信网络，图中边的权值表示两个结点之间通信时的消耗，组播树其实就是带权无向图中的最短路径树。然而，在通信网络中，由于某些原因会导致结点间的物理链路断开或数据丢失，这时我们不仅需要选择新的组播树来保证信号源点到每个结点间的链路通畅和数据完整，而且还要保证整个的通信费用最小，因此最短路径树在不确定图中的研究具有十分重要的意义。本文主要对不确定图中的最短路径树算法进行深入研究，并获得如下进展：
　　（1）因为不确定图中的边存在不确定性，所以在研究不确定图中最短路径树问题时已经不能使用确定图中的方法，我们提出了不确定图中的最短路径树概念，并在此基础上给出了最优最短路径树概念。最优最短路径树是指权值最小的最短路径树。我们借助边变换思想设计了不确定图中最优最短路径树算法，算法主要通过不断换入权值小的边来共享路径，进而降低最短路径树的权值，最终得到最优最短路径树，然后通过减少边变换判断次数可以有效的提高该算法的运行效率。
　　（2）对最短路径树在不确定图中的可靠性进行了分析。所有可靠蕴含图的可靠性的和就是最短路径树的可靠性，并提出了一种新的计算方法来计算最短路径树的可靠性，在此基础上我们给出了最可靠最短路径树的概念。最可靠最短路径树是指不确定图中可靠性最高的最短路径树。我们借助边变换思想设计了不确定图中最可靠最短路径树算法。算法主要通过不断换入存在概率高的边来提高最短路径树的可靠性，进而得到最可靠最短路径树，然后通过减少边变换判断次数可以有效的提高该算法的运行效率。
　　最后，通过对实例进行分析和相关的实验验证，证明了最优最短路径树算法和最可靠最短路径树算法的可行性，我们能够完全正确的得到问题的解。

目录

声明

第1章 引言

1.1 研究背景以及意义

1.2 研究现状

1.3 主要内容

1.4 本文的结构安排

第2章 相关的基础知识

2.1 确定图

2.2 不确定图

2.3 最短路径树问题

2.4 本章小结

第3章 不确定图中的最优最短路径树算法

3.1 问题的定义

3.2 基本方法

3.3 最优最短路径树算法

3.4 实例分析

3.5 算法优化

3.6 算法实验

3.7 本章小结

第4章 不确定图中的最可靠最短路径树算法

4.1 问题定义

4.2 基本方法

4.3 最可靠最短路径树算法

4.4 实例分析

4.5 算法优化

4.6 算法实验

4.7 本章小结

第5章 总结与展望

参考文献

致谢

附录A （攻读硕士学位期间发表的论文）

附录B （攻读硕士学位期间参与的科研项目）

附录C （攻读硕士学位期间获奖情况）