For the first time proposed: a method for representing the projections of a graph in computer memory and a description based on it of a quick search for shortest paths in unweighted dynamic graphs. The spatial complexity of the projection description does not exceed $(d + 1)\times n$ words, where $d$ is the diameter and $n$ is the number of vertices of the graph. The temporal difficulty of finding one shortest path between two vertices does not exceed d steps with the duration of elementary time of sampling a machine word. The solution can be applied in time delay-critical routing protocols of computer networks and supercomputers.
翻译:首次提出: 一种在计算机内存中代表图形预测的方法, 以及一种基于该方法的描述, 即快速搜索未加权动态图形中最短路径。 投影描述的空间复杂性不超过$( d + 1) + 1 乘以n$ 单词, 其中美元是直径, 美元是图的顶点数。 在两个顶点之间找到一条最短路径的时间困难不超过在机器单词取样的基本时间段的 d 步。 解决方案可以应用于计算机网络和超级计算机的时间延迟关键路由协议 。