Досліджується задача побудови локально-оптимального орієнтовного графа з навантаження ребрами, коли кожному ребру приписана фіксована числова вага. Локальна оптимальність або стабільний незмінний стан поточної розмітки графа дає загальний метод розв'язання багатьох задач, пов'язаних з оптимізаційним пошуком у графах. Показано як із розв’язання загальної задачі побудови локально-оптимального графа випливає задача знаходження шляхів найменшої ваги (вартості). Серед нових застосувань вказується вирішення проблеми асоціативного пошуку в комп’ютерній лінгвістиці (образне мислення) та швидкої взаємної автентифікації в коаліційних угрупуваннях.