Tratamos da generalização do problema da geração de caminho mínimo, no qual não apenas um, mas vários caminhos de menores custos devem ser produzidos. O problema dos k-menores caminhos consiste em listar os k caminhos de menores custos conectando um par de vértices. Esta dissertação trata de algoritmos para geração de k-menores caminhos em grafos simétricos com custos não-negativos, bem como algumas implementações destes. / We consider a long-studied generalization of the shortest path problem, in which not one but several short paths must be produced. The k-shortest (simple) paths problem is to list the k paths connecting a given source-destination pair in the digraph with minimum total length. This dissertation deals with k-shortest simple paths algorithms designed for nonnegative costs, undirected graphs and some implementations of them.

Tratamos da generalização do problema da geração de caminho mínimo, no qual não apenas um, mas vários caminhos de menores custos devem ser produzidos. O problema dos k-menores caminhos consiste em listar os k caminhos de menores custos conectando um par de vértices. Esta dissertação trata de algoritmos para geração de k-menores caminhos em grafos simétricos com custos não-negativos, bem como algumas implementações destes. / We consider a long-studied generalization of the shortest path problem, in which not one but several short paths must be produced. The k-shortest (simple) paths problem is to list the k paths connecting a given source-destination pair in the digraph with minimum total length. This dissertation deals with k-shortest simple paths algorithms designed for nonnegative costs, undirected graphs and some implementations of them.

No description available.

This thesis proposes a novel and efficient method (Method of Evolving Junctions) for solving optimal control problems with path constraints, and whose optimal paths are separable. A path is separable if it is the concatenation of finite number of subarcs that are optimal and either entirely constraint active or entirely constraint inactive. In the case when the subarcs can be computed efficiently, the search for the optimal path boils down to determining the junctions that connect those subarcs. In this way, the original infinite dimensional problem of finding the entire path is converted into a finite dimensional problem of determine the optimal junctions. The finite dimensional optimization problem is then solved by a recently developed global optimization strategy, intermittent diffusion. The idea is to add perturbations (noise) to the gradient flow intermittently, which essentially converts the ODE's (gradient descent) into a SDE's problem. It can be shown that the probability of finding the globally optimal path can be arbitrarily close to one. Comparing to existing methods, the method of evolving junctions is fundamentally faster and able to find the globally optimal path as well as a series of locally optimal paths. The efficiency of the algorithm will be demonstrated by solving path planning problems, more specifically, finding the optimal path in cluttered environments with static or dynamic obstacles.

In this thesis, we introduce three new approaches for solving the single source shortest path (SSSP) problem in nearly acyclic directed graphs, and algorithms based on these approaches. In the first approach, we extend a technique of strongly connected components (sc-components) decomposition by Takaoka [23], and the generalized decomposition approach is called a higher-order decomposition. According to Takaoka's definition of acyclicity, the degree of cyclicity of a graph G, cyc(G), is defined by the maximum cardinality of the strongly connected components of G. Based on the higher-order decomposition, we give a generalization of Takaoka's definition of acyclicity. That is, the degree of cyclicity cych(G) is the maximum cardinality of the hth order strongly connected components of G, where h is the number of times that the graph has been decomposed. Then, the original definition introduced by Takaoka [23] can be presented as: The degree of cyclicity cyc(G) is the maximum cardinality of the 1th order strongly connected components of G. The second approach presents a new method for measuring acyclicity based on modifications to two existing methods. In the new method, we decompose the given graph into a 1-dominator set, which is a set of acyclic subgraphs, where each sub-graph is dominated by one trigger vertex. Meanwhile we compute sc-components of a degenerated graph derived from triggers. Using this preprocessing, we can efficiently compute the single source shortest paths (SSSPs) for nearly acyclic graphs in O(m + r logl ) time, where r is the size of the 1-dominator set, and l is the size of the largest sc-component. In the third approach, we modify the concept of a 1-dominator set to that of a 1-2-dominator set, and achieve O(m + r²) time to compute a 1- 2-dominator set in a graph. Each of acyclic sub-graphs obtained by the 1-2-dominator set are dominated by one or two trigger vertices cooperatively. Such sub-graphs are potentially larger than those decomposed by the 1-dominator set. Thus fewer trigger vertices are needed to cover the graph, that is, rʹ ≤ r, where rʹ is the number of triggers in the 1-2-dominator set. When rʹ is much smaller than r, we can efficiently compute SSSPs in O(m + rʹlogrʹ) time.

In recent years the growth in demand for multimedia applications delivered over a network has been extensive illustrated by the phenomenal expansion of the World Wide Web in today's Internet. Increasing amounts of electronic information are presented in a multimedia format and delivered over networks, which generates increased traffic demands. In short, future networks will not only comprise multiple, interconnected data transport platforms but will also need to handle an increasing range of distributed multimedia services, delivered to a diverse user community that is increasingly becoming mobile.

The problem of computing K shortest loopless paths, or ranking of the K shortest loopless paths between a pair of given vertices in a network is a well-studied generalization of shortest path problem. The K shortest paths problem determines not only one shortest path but the K best shortest paths from s to t in an increasing order of weight of the paths. Yen’s algorithm is known to be the efficient and widely used algorithm for determining K shortest loopless paths. Here, we introduce a new algorithm by modifying the Yen’s algorithm in the following way: instead of removing the vertices and the edges from the graph, we store them in two different sets. Then we modified the Dijkstra’s algorithm by taking these two sets into consideration. Thus the algorithm applies glass box methodology by using the modified Dijkstra’s algorithm for our dedicated purpose. Thus the efficiency is improved. The computational results conducted over different datasets, shows the proposed algorithm has better performance results.

We address the problem of all-pairs shortest time communication of messages in futuregeneration 6G networks by modeling the highly dynamic characteristics of the network using a temporal graph. Based on this model, an elegant technique is proposed to devise an algorithm for finding the all-pairs shortest time paths in the temporal graph that can be used for all-pairs internodes communication of messages in the network. The proposed algorithm basically involves computations similar to only two matrix multiplication steps, once in the forward direction and then in the backward direction.

Shortest path problems arise in a variety of applications ranging from transportation planning to network routing among others. One group of these problems involves finding shortest paths in graphs where the edge weights are defined by probability distributions. While some research has addressed the problem of finding a single shortest path, no research has been done on finding multiple paths in such graphs. This thesis addresses the problem of finding paths for multiple robots through a graph in which the edge weights represent the probability that each edge will fail. The objective is to find paths for n robots that maximize the probability that at least k of them will arrive at the destination. If we make certain restrictions on the edge weights and topology of the graph, this problem can be solved in O(n log n)time. If we restrict only the topology, we can find approximate solutions which are still guaranteed to be better than the single most reliable path.

[Abstract]: This is a project to implement a Mice and Elephants queueing discipline, which favoursshort flows over long flows, on Linux. The project has three aims. The first aim is toproduce a prototype Mice and Elephants router for the purpose of further evaluation ofthe Mice and Elephants strategy and the Shortest Job First strategy. The second aim is tomake a contribution to Linux by making my implementation as code that is both fit fordistribution with Linux and useful in a small business or domestic setting. The third aimis to explore and document a method of creating Linux queueing disciplines in general.