[Bargest]

Ну базы - это, конечно, круто. Но для графа достаточно и текстового файлика. Сначала названия, дальше - строки по 2 id и расстоянием. Пример:

3 // количество городов
Москва
Питер
Киев
0 1 600 // связь города 0 с городом 1 длиной 600 км.
0 2 500

Можно все то же самое и в базе - таблица соответствия id<->название, и таблица id1|id2|length. Можно и страну приделать в первую таблицу, или же прилепить туда id страны, а саму страну в отдельной таблице - зависит от задачи. Но так, как ты предложил, придется при построении графа сравнивать все время строки (имена городов), а поле id оказывается лишним.
После читаем про графы, к примеру - алгоритм Дейкстры (см. Гугл и Википедию, там даже гифка-иллюстрация есть). Можно просто из каждой вершины двигаться по всем путям, начиная с кратчайшего, и запоминать длину пути; если зашли в тупик - откат на вершину назад, а если дошли до нужной вершины - это и есть кратчайший путь.
Если же есть прямой путь из каждого города в каждый - то просто

Код:

select length from table where id1 = index1 and id2 = index2

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