Problems of advance

The problems of advance are traditional problems of the Graph theory. The objective is to calculate a road between tops of a graph which minimizes or maximizes a certain economic function.

The most traditional problem consists in looking for the way which minimizes the sum of the valuations of the crossed edges. There exist polynomial algorithms to solve this problem, like the Algorithme of Dijkstra. On the other hand, when one adds additional constraints like windows of time, the problem becomes Np-difficult.

Algorithms of resolution of the traditional problem of shorter way

When the graph does not comprise a cycle, one will use the algorithm of Bellman. When the valuations are positive, the algorithm most usually used is the Algorithme of Dijkstra. However, it seems that method known as in English threshold method , proposed by Glover, Glover and Klingman in 1984, is more effective in practice, even if its complexity is higher.

Algorithms of resolution of the problem of shorter way with windows of time

Several algorithms were proposed to solve this problem.

External bond

Six dismantle Wikipedia off: Web page calculating the distance between two articles of Wikipedia (english language version), and showing the way between these two articles

Random links: