Нужно найти самый короткий путь между двумя вершинами ориентированного графа.
Знаю то нужно пройти граф через Breadth First Search, но не знаю как посчитать этот путь.


Заранее благодарю за помощь.

Это сообщение отредактировал(а) sas8899 - 26.12.2007, 20:35

на данный момент для каждой вершины viz хранит одно из двух значений:
0 - не посещалась
1 - посещалась
можно расширить
-1 - не посещалась
L>=0 - посещалась и кратчайшее расстояние = L
т.е. вместо viz[j]=1 можно писать viz[j]=viz[s[iss]]+1

P.S.
всё-таки я бы советовал более красноречиво называть переменные 

P.P.S.
на всякий случай уточню: все рёбра имеют одинаковую длину?

maxim1000, да все ребра имеют одинаковую длину.

P.S Что имеешь ввиду насчет переменных? Как правильно их называть?

P.P.S. Отредактировал код, это ты имел ввиду?

Это сообщение отредактировал(а) sas8899 - 26.12.2007, 19:01

ну хотя бы x -> start, y -> finish

вот с этого файла у меня создается граф

7
0 1 0 0 0 0 0
1 0 1 0 0 0 0
1 0 0 1 0 0 0
0 0 1 0 1 0 0
1 0 0 0 0 1 0
0 0 0 0 0 0 1
0 0 0 0 0 0 0

когда существует путь от вершины Х к вершине У то все считает нормально, а вот к примеру есть путь от 4 до 5, но обратно нету, и если ввожу х=5 и у=4 то выдает ответ 4, хотя никак из 5 в 4 не попасть.

Добавлено через 1 минуту и 3 секунды
maxim1000, хорошо   буду иметь ввиду на будующее, спасибо  

ну так это надо отладчиком пройтись
главное: представлять в голове, как оно должно работать, тогда не составляет трудности в любой момент понять, какие должны быть значения в массивах и сравнить их с теми, которые в программе, а значит, и найти место, где программа начинает вести себя не так, как хотелось бы

Добавлено через 3 минуты и 37 секунд

это зависит от того, как задаётся матрица
если "откуда" откладывается по горизонтали, а "куда" - по вертикали, то из 5 в 4 как раз можно попасть

Добавлено через 3 минуты и 52 секунды
т.е. стоит ещё и проверить, правильно ли читается матрица...

Вот как у меня читается матрица.

P.S. Отсчет вершин начинается с 0.

Добавлено через 11 минут и 57 секунд
maxim1000, все спасибо я разобрался в чем дело.

P.S. Исправил код, если кому-то еще понадобится.

Это сообщение отредактировал(а) sas8899 - 26.12.2007, 20:27