Patent ID: 7406047
Filing Date: 2008-07-29
Classification: G06Q,H04L

Abstract:
1. A method of computing shortest paths in a weighted graph having vertices and an adjacency matrix with memory resources and a processor comprising: (a) selecting integer weights; (b) carrying out a series of incrementations, an incrementation comprising finding a set of vertices to which one may arrive from a given set of vertices; (c) carrying out a series of decrementations, a decrementation comprising finding a set of vertices from which one may go to arrive to a given set of vertices; (d) causing the incrementations and decrementations to be carried out in any order; (e) transforming vectors of increments/decrements in paths, the paths making up set E (f) selecting n-uple of paths C of lowest cost among a set of paths E (g) calculating N (h) computing iteratively, while N (i) determining paths of lowest weight based on C.