Un paysage écologique peut être modélisé comme un graphe dirigé G=(V,A) dont les sommets représentent les zones d'habitat du paysage et les arcs représentent les connexions entre ces zones. Chaque sommet possède un poids indiquant la qualité écologique de la zone qu'il représente et chaque arc est associé à une longueur qui représente la difficulté pour un organisme d'effectuer le déplacement correspondant. La Probabilité de Connectivité du paysage est calculée à partir des distances de plus court chemin dans ce graphe pondéré et est souvent utilisée par les écologues pour évaluer la connectivité du paysage et identifier les zones à prioriser pour la conservation ou la restauration.

Nous nous intéressons au problème de la maximisation de la Probabilité de Connectivité d'un paysage sous contrainte budgétaire, c'est à dire la recherche de la meilleure combinaison d'options d'aménagement parmi un ensemble donné, chaque aménagement étant modélisé par une modification des pondérations du graphe.

Nous donnons une formalisation en PLNE pour ce problème et proposons une technique de prétraitement des plus courts chemins permettant de réduire significativement la taille des programmes linéaires à résoudre. Pour mettre en oeuvre ce prétraitement de manière efficace, nous donnons un algorithme en temps O(|A| + |V| log |V|) pour résoudre le problème suivant : étant donné un ensemble de scénarios caractérisés par le choix des longueurs possibles des arcs et un arc (u,v), calculer l'ensemble des sommets t tel que (u,v) est sur un plus court chemin de u à t pour tout scénario.