La notion de graphes augmentés a été introduite dans le but d'analyser le phénomène des "six degrés de séparation entre individus" observé empiriquement par le psychologue Milgram dans les années 60. De façon formelle, un graphe augmenté est une paire (G,\varphi), où G est un graphe et \varphi une collection de distributions de probabilité {\varphi_{u}, u\in V(G)}. Un lien supplémentaire est attribué à chaque noeud u\in V(G), pointant vers un noeud v, appelé contact longue-distance de u. La destination v de ce lien est choisie aléatoirement selon Pr{u->v}=\varphi_{u}(v). Dans un graphe augmenté, le routage glouton correspond au processus de routage sans mémoire dans lequel chaque noeud intermédiaire choisit parmi ses voisins (dont le voisin supplémentaire) celui qui est le plus proche de la cible selon la distance mesurée dans le graphe de départ G, et lui envoie le message. Grossièrement, les graphes augmentés ont pour but de modéliser la structure des réseaux sociaux tandis que le routage glouton a pour but de modéliser le procédé de recherche utilisé dans l'expérience de Milgram. Notre objectif est de concevoir des schémas d'augmentation universels efficaces, c'est-à-dire des schémas d'augmentation qui attribuent à tout graphe G une collection de distributions de probabilité \varphi telle que le routage glouton dans (G,\varphi) soit rapide. Il est connu que le schéma d'augmentation uniforme \varphi_{unif} est un schéma universel qui garantit que, pour tout graphe G de n noeuds, le routage glouton dans (G,\varphi_{unif}) s'achève en O(\sqrt{n}) étapes en espérance. Notre résultat principal est la conception d'un schéma d'augmentation universel \varphi tel que le routage glouton dans (G,\varphi) s'achève en \Otilde(n^{1/3}) étapes en espérance pour tout graphe G de n noeuds. Nous montrons également que sous l'hypothèse d'un modèle plus restreint, la borne \sqrt{n} ne peut être diminuée.