Algoritmo Greedy - Spanner (Path - Greedy Spanner, PG (S,t))
Este algoritmo construye, dado un conjunto S y un valor t>1, un t-spanner de forma voraz.
En primer lugar se ordenan las aristas del grafo completo sobre el conjunto S de menor a mayor longitud. Luego se procesan las aristas en este orden de una en una. La idea básica es que una arista uv formará parte del grafo si la distancia entre u y v (en el grafo construido hasta ese momento) es mayor que t·|uv|
Si t = n – 1, el algoritmo obtiene el árbol generador mínimo del grafo completo Ks. Este algoritmo NO siempre computa un t-spanner de mínimo peso.