Есть карта дорожной сети, на которой показаны улицы. Их можно определить по цвету. Точнее, если не серый, то в данном месте проходит улица. Правда, еще нужно учитывать толщину. Как можно преобразовать всю эту сеть в граф, чтобы можно было определить расстояния между 2 точками по улицам, и как найти потом самое короткое расстояние среди всех возможных маршрутов между 2 точками?

Исползуй алгоритм Дейкстры.

Спасибо. Сложнее будет преобразовать саму сеть в граф. Можно попиксельно перебирать картинку и что-то строить, но способ довольно муторный. Может, есть идеи? Особенно проблема с кривыми улицами

  

Поиск в графе вы все равно при помощи волны будете делать так что особого смысла переводить в граф я не вижу.  И сразу использовать волновой алгоритм на картинке. А если хотите строить граф то опять таки волновой алгоритм(в сети глянь волновой алгоритм скелетизации).

Примерный смысл поясните, как предлагается это делать. Допустим, у вас есть такая карта улиц.

Добавлено через 5 минут и 29 секунд
Похоже, этот алгоритм весьма сложен. И для моей задачи можно обойтись чем-то другим. Просто усредненное что-то брать (расстояния и т.п.). В общем, граф долго делать...

motorway,  Обычный алгоритм волны который в интернете сто раз описан.
Берем точку на карте смотрим если желтого цвета то начинаем выполнять алгоритм.
Помечаем эту точку как пройденную ставим время 0. пробуем 4 соседних точек если они  желтые и не помеченные то заносим в массив.
Рекурсивно вызываем нашу функцию поиска. Она перебирает все точки смотрит для каждой есть ли соседи уже помеченные и выбирает с наименьшим числом заносим это число+1. и тд пока не дойдем до конечной. 

Обход в глубину получается.

Это сообщение отредактировал(а) Pavia - 1.10.2009, 11:37