Оптимизация алгоритма поиска

[Волкодав]

Здравствуйте, решаю следующую задачу:
Задан граф с K вершинами и отметками на ребрах – целыми числами от 1 до K. В базе данных хранится N векторов длины M, компоненты которых – номера вершин графа - числа от 1 до K. Значения разных компонент вектора могут совпадать. Запрос – такой же вектор длины M. Требуется найти в базе данных вектор, ближайший к запросу. Расстояние между двумя векторами (a1,..,aM) и (b1,..,bM) вычисляется как сумма от 1 до M расстояний d(ai,bi) между вершинами графа с номерами ai и bi.
Пусть мне известна таблица расстояний между вершинами, и я могу непосредственно сравнивать вектор запроса и вектора в базе данных. Делаю это перебором векторов из базы, что очевидно)). Но теперь мне нужно оптимизировать этот перебор. Пока не представляю как это можно сделать...помогите с идеями, заранее благодарю!

[Sasha_Smirnov]

«Метод северо-западного угла» остался в голове лишь как название…

Моё: VBA, массивы (извините, если не в тему… ностальгия!).

Sazary тут упомянул также алгоритм Прима-Краскала (это вроде ближе) — и граф симпатичный приложен.

Ну и совсем горячо: Поиск всех вариантов в таблице алгоритмом Дейкстры от Михаила Чехова!

[Utkin]

Вам нужно кратчайшее расстояние на графе?