(с++) Кратчайший путь в графе

[Uefa]

Сообщение от SaLoKiN

а разве для такой картинки матрица смежности будет такой?
0, 1, 1, 0,
0, 0, 1, 0,
1, 0, 0, 1,
0, 1, 0, 0,
и вроде для нахождения кратчайшего пути граф должен быть взвешенный...или нужно найти путь по минимальному количеству пройденных вершин от start to end?

На картинке я привел простейший пример, для понимания того, что у меня не получается. Граф в программе будет вводится с клавиатуры через матрицу смежности (либо браться из текстового файла). Кратчайший путь находим по минимальному количеству пройденных ребер.

[Poma][a]

и вроде для нахождения кратчайшего пути граф должен быть взвешенный...или нужно найти путь по минимальному количеству пройденных вершин от start to end?

О Боги!
Граф может быть каким угодно..
Да! Именно так!

BFS будет такой

while (!empty(q))
{
     v = pop(q);
     for (i = 1; i <= n; i++)
         if (adj[v][i] == 1 && p[i] == INF) 
         {
              push(q, i);
              p[i] = p[v]+1;
         }
}

[Uefa]

Сообщение от Poma][a

О Боги!
Граф может быть каким угодно..
Да! Именно так!

BFS будет такой

while (!empty(q))
{
     v = pop(q);
     for (i = 1; i <= n; i++)
         if (adj[v][i] == 1 && p[i] == INF) 
         {
              push(q, i);
              p[i] = p[v]+1;
         }
}

А можно еще расшифровать? Т. е. q это очередь? Пока очередь не пустая, присваиваем текущей вершине pop(q)... это как? pop() как я знаю это удалить элемент из очереди, void функция, как мы можем ее присвоить? И что такое INF?

p.s. видимо v = pop(q) означает, что берем первый элемент из очереди, с помощью цикла for перебираем все вершины графа и если находим ребро и ... что все-таки такое INF? Потом кладем в очередь смежную вершину и какие-то махинации с массивом p, объясните пожалуйста подробнее.

[Poma][a]

Т. е. q это очередь?

да

pop() как я знаю это удалить элемент из очереди

Вполне может быть.
Всё зависит от реализации очереди..
Есть top - берет элемент, не удаляя
А есть pop - удаляет элемент
В моей реализации я забабахал и top и pop в одну функ

И что такое INF?

Плюс бесконечность

[Uefa]

Сообщение от Poma][a

да

Вполне может быть.
Всё зависит от реализации очереди..
Есть top - берет элемент, не удаляя
А есть pop - удаляет элемент
В моей реализации я забабахал и top и pop в одну функ

Плюс бесконечность

Берем первую вершину из очереди, удаляем ее из очереди, с помощью цикла for ищем смежные вершины, если находим добавляем в очередь... а что за массив p и для чего мы сравниваем его с бесконечностью?

[Poma][a]

В P хранится путь..

и для чего мы сравниваем его с бесконечностью?

Потому что, если для этой вершины найден, нечего нам его снова искать.. (войдем в бесконечный цикл)..