用摹矩阵寻求网络的最短路

应用了半城、摹矩阵和优选半域等概念,把摹矩阵的计算运用到图论中的寻求负权网络中的最短路以及寻求网络中各点间的最短路问题上。实例的计算结果表明,这是一种计算简便,行之有效的方法.     

含负权有向图最短路问题的一种新算法

Dijkstra算法是求解最短路问题的一种经典算法，但是它的缺点是不能用来求解含有负权的最短路问题。本文对图论中含有负权的最短路问题进行研究，提出了一种新算法，将含有负权的最短路问题先转化为不含负权的最短路问题，最后再利用Dijkstra算法求解，并用实例验证该算法的有效性，具有一定的现实意义。     

Dijkstra算法在权矩阵上的实现

Dijkstra算法是求解最短路问题的有效算法,一般都是在图上进行直接标号,文章探讨了直接在权矩阵上使用该算法求出最短路径及其长度的方法。     

状态转移问题的图论法建模

针对带有约束条件的一类状态转移问题，提出了图论建模法，将这类状态转移问题转化为利用Ｄｉｊｋｓｔｒａ算法求最短路，并通过典型实例论述了这种方法的建模技巧及求解法．该方法比逻辑思索的结果容易推广，能在本质上体现图论方法的优势．     

基于网络拓扑的交通最优路线选择模型

从网络拓扑的角度,将交通最优路径搜索问题转化为图论中的最短路径搜索问题,并通过对最短路径搜索算法的分析和构建,结合分块矩阵和分类思想,提出了一套求解城市公交地铁道路网络两点间最优路径的算法,该算法具有较强的拓扑稳定性,可以扩展应用到城市交通地理信息系统（TGIS）领域。     

枢纽内确定货运站位置的几种方法

本文就此问题,搬开常规的定性分析法,以定量的计算介绍三种方法。一、质点重心计算法:当货源集散点间无通路时,模拟成求 n 个质点重心位置的数学模型,二,质点比较法:当货源集散点间有通路时,运用“以少靠多”的原则和“图论”知识的丢边法近似的求其解;三、网络矩阵法:运用图论中最短路的求解和矩阵的运算特点给出精确的确定方法。此法为展示通道径路,在矩阵各元中注有下标。本文最后还提供枢纽内设置两个以上货运站时,其最有利位置的确定方法的思路。     

图的路径运算矩阵与哈密顿回路等路径问题

从简单图的邻接矩阵定义了初始路径运算矩阵和一般路径运算矩阵,并定义了一般路径运算矩阵的加法和乘法运算,通过这些运算可以直接求简单图的最长路、最短路、任意两点之间的通路及具有长度约束的路径问题,还可以检测简单图哈密顿回路及计算所有哈密顿回路,结果都显示在最后的路径运算矩阵上。证明了一般路径运算矩阵的幂长公式并得到了简单图存在哈密顿回路的充要条件,分析了矩阵乘法运算的总时间复杂度,结果表明本算法比其他同类方法计算量大大减少,为图论相关路径问题研究提供了一个新的研究方法。     

用原始－对偶算法求解过指定顶点的最短路

建立了赋权有向图中两顶点间过指定顶点的最短路问题的线性规划模型，用原始－对偶算法给出一个求解方法     

周期性时变网络中粮食物流优化探讨

粮食是国家重要的经济和战略物资,粮食调运问题是国家粮食管理部门和粮食企业急需解决的重要问题.针对粮食运输的特点,提出多周期时变网络中物流调度的最优化问题,从数学模型及算法设计方面开展研究,建立基于(0,1)整数规划的周期性时变网络最短路问题的数学模型.为便于求解,将其转化为图论模型,从而得到多项式时间算法.     

关于非线性最优化的一种直接搜索方法

一、引言考虑如下无约束非钱性最优化问题: 如所周知,这种问题的解决,有直接搜索方法与间接方法两类。所谓直接搜索法,即从初始点出发,只根据若干点函数值大小,逐步寻找到使函数值下降的新点,而最终逼近最优点,即函数值最小的点。直接搜索方法在函数的梯度向量及二阶导数矩阵难以计算时,即通常行之有效的间接方法难以奏效的情况下,就特别重要了。     

邻接矩阵求带权图中最短通路

通过对带权邻接矩阵定义一种运算,计算n阶简单带权图中任意两点之间步长为1,2,…,n -1的最短通路长度,逐步比较,确定通路所过各边权值之和最小的即最短路径。在计算的过程中用矩阵记下最短路径所经过的所有结点,最后验证了其在无向和有向简单带权图中的有效性。     

求解路网最短路的快速算法

探讨了最短路算法在交通分配中的重要地位。在此基础上．比较了现有最短路算法的优缺点,同时提出了一种改进的矩阵迭代算法．并利用该算法对一简单路网进行了验证。     

矩阵方法求赋权图中最短路的算法

目的 给出一些计算赋权图中任意两个节点之间最短路的算法。方法 利用矩阵方法。结果 给出了赋权图中任意两点之间最短路的算法；任意两点之间在含有最少边数情况下的最短路算法；赋权图中的所有最短路算法，以及前N条最短路的算法。结论 所研究的算法解决了传统算法的某些不足，因基于矩阵运算，程序设计简单，实用性强。     

公共交通系统最佳路径算法

在分析城市道路网络最短路径算法(SP算法)和公交网络的特点的基础上,提出公共交通系统最佳路径算法.首先引入直达矩阵(T矩阵)和最小换乘矩阵(Q矩阵),讨论公交网络节点间换乘问题,得出最少换乘算法.利用Q矩阵确定节点间最少换乘次数,评价公交网络方便可达性.其次结合最少换乘算法,对最短路径算法(Dijkstra算法)进行改进.在标号过程中,利用Q矩阵对待检验T标号点进行筛选,减少T标号计算量,得到一条综合考虑路径长度和换乘的最佳路径.最后用一个简单的算例进行验算,说明该算法适用于一般公交网络,特别是换乘代价较高的公交网络.     

ATE开关矩阵最短路径搜索算法

 开关矩阵作为信号传递的枢纽,在自动测试设备内部扮演着极其重要的角色。当信号源节点与目标节点之间距离最短时,信号才能最有效地传输。基于开关矩阵的物理模型,结合图论知识,构造了开关矩阵的数学模型。针对通路继电器最少、系统可靠性最高2 种情形,把路径最短问题抽象成无权图和有权图的最短路径搜索问题,分别采用广度优先搜索（BFS）算法和Dijkstra 算法进行研究,并提出改进型算法。通过具体实例,建立模型并应用改进算法予以实现。改进算法应用于ATE 通用适配器的开发研制和自动测试设备软件平台的设计,可实现最佳测试路径的快速自动搜索,具有工程实践价值。     

基于最短路径和样点插值的城市基准地价GIS系统

研究并介绍了几种主要的基准地价测算方法,其中样点法是一种快速直观、现势性好的新方法;样点法通常需要基于最短路径来进行.本文对传统的最短路径方法进行了补充,计算得到了更为精确的空间任意两点之间的最短距离,提高了地价衰减模型的计算精度;基于最短路径计算结果,采用移动平均法进行空间插值,设计并实现出相应的G IS系统,应用于实际的基准地价计算与结果表现.     

多面体面上任意两点间最短路径算法

提出计算多面体面上任意两点之间最短路径的算法:近似算法、最短路径或近似最短路径算法.近似算法的思想是采用将折线不断嵌入三角形串上的方法,而另2个算法则是通过特定法线寻找三角形串,而且将这些三角形旋转到同一平面上,从而得到最短路径.前者的时间复杂性为O(n),而后者的时间复杂性分别是O(n2)及低于O(2nn2).     

赋权图上最短路径的一种简便算法

在不考虑负回路的前提下,给出了在含有负权的赋权图上求任意两点间最短路径的一种简便算法,此算法既适用于有向图又适用于无向图,并且可据此算法找到最短路径。     

关键路径的矩阵计算公式

在研究最短通路问题的基础上,通过＂最短通路＂与＂关键路径＂的对比研究,给出PERT/CPM问题（计划评审技术图/关键路径方法的简称）相应的＂对偶＂的矩阵定义及＂对偶＂运算法则,进而推出＂对偶＂的计算公式.     

最短路径算法在校园地理信息系统中的应用

本文介绍了求最短路径的迪杰斯特拉算法和弗洛伊德算法,并以地理信息数据为基础,以网络模型图为背景,利用弗洛伊德算法建立邻接矩阵D和路径矩阵P,最终求出任意两个位置的最短路径以及中间所经过的中转点。