Warning: Undefined variable $PHP_SELF in /customers/9/8/1/usmart.dk/httpd.www/bachelor/index.php on line 2
Warning: Undefined array key "word" in /customers/9/8/1/usmart.dk/httpd.www/bachelor/index.php on line 5
Warning: Undefined array key "svar" in /customers/9/8/1/usmart.dk/httpd.www/bachelor/index.php on line 6
Warning: Undefined array key "valg" in /customers/9/8/1/usmart.dk/httpd.www/bachelor/index.php on line 7
Spanners

The most time-consuming parts of the algorithm are sorting the pairs of vertices, and finding a shortest path in the graph. Luckily, well known, effective algorithms exist to solve these problems.

Sorting

L01:
Sort all pairs of vertices in non-decreasing order
by their euclidian distance.
···

In L01 of the greedy algorithm, all pairs of vertices are sorted. A graph with n vertices have ½·n·(n-1) possible combinations of two vertices. Or, put in big O notation, O(n^{2}) possible pairs.
Sorting p elements can b done in O(p·log p) time using Merge Sort or Quicksort.
Thus line L01 of the pseudocode has a complexity of O(n^{2}·log n^{2}).

Finding a shortest path

···
L03:
Find a shortest path between the two vertices.
···

Dijkstra's algorithm is able to find a shortest path between two vertices in a weighted graph with non-negative edge weights in O(V·log V + E) time. A graph constructed by the greedy algorithm has at most V^{2}/2 edges (for t=1).
However, for t>1 t-spanners are considered to be sparse, that is, to have O(V) edges. The cost of finding a shortest path in such a graph is thus O(V·log V + V) = O(V·log V).

Complexity

L03 to L10 are run once for each of the O(n^{2}) pairs of vertices.
Apart from L03 all of these lines have a complexity of O(1). The whole loop thus has a complexity of O(n^{3} · log n). Since this is higher than that of L01, it is also the complexity of the whole algorithm.

Improving the complexity

Different adjustments can be done in order to improve the complexity of the greedy algorithm.

One way is to minimize the number of computations of a shortest path. It is sufficient to know if a satisfactory short path between two vertices exists, not how long the shortest path is. By keeping track of the already computed distances, it is often possible to find a other paths by combining these. If paths exist from A to B and from B to C and the combined weight of these is small enough, it is not necessary to compute the shortest path from A to C.