Кратчайший путь в графе

Мой график реализован следующим образом:

struct node{
    string ID;
    vector<string> neighbors;

}

struct graph{
    vector<string> nodes;
}

nodes — вектор узлов. Каждый узел содержит свой идентификатор и вектор идентификаторов всех его соседей (узлов, на которые он указывает).

Есть ли способ применить алгоритм Дейкстры или Беллмана-Форда, чтобы найти кратчайший путь между двумя узлами? Найти повторяющийся цикл? Как бы я это сделал?

РЕДАКТИРОВАТЬ: sturcts были случайно названы одинаково.


c++ algorithm shortest-path dijkstra bellman-ford
person dj3000    schedule 28.01.2014    source источник
comment
Если у вас есть список смежности - да, это возможно.   -  person Anirudh Ramanathan    schedule 28.01.2014
comment
Я не думаю, что это список смежности, я уточнил свой код.   -  person dj3000    schedule 28.01.2014
comment
Обе ваши структуры имеют одинаковое имя. У вас есть где-нибудь вектор node или что-то подобное? Почему бы вам не использовать vector<node*> вместо vector<string> для соседей?   -  person    schedule 28.01.2014
comment
как получить узел, есть ли у вас глобальная карта id-›node?   -  person Ezra    schedule 28.01.2014
comment
Поиск элементов приведет к пустой трате времени при таком отображении. Должно быть легко составить список смежности vector<node*>, как предложил @Nabla.   -  person Anirudh Ramanathan    schedule 28.01.2014
comment
с хеш-таблицей поиск должен быть O (1)   -  person Ezra    schedule 28.01.2014
comment
Это похоже на домашнее задание; пожалуйста, покажите нам свою попытку?   -  person jnnnnn    schedule 28.01.2014
comment
Извините, исправил структуры. Это не проблема HW. Моими основными ссылками являются статьи википедии Дейкстры и Беллмана-Форда, но у меня возникли проблемы с преобразованием псевдокода, чтобы он соответствовал моему набору задач.   -  person dj3000    schedule 28.01.2014
comment
@ dj3000 Вы до сих пор не ответили на самый важный вопрос: где находятся экземпляры node и почему вы ссылаетесь на узлы строкой, а не адресом/указателем узла?   -  person    schedule 28.01.2014
comment
@Nabla Я ссылаюсь на узлы строкой, чтобы соответствовать полезной нагрузке каждого узла. Я предполагаю, что было бы более разумно создать вектор соседей как vector‹node*›, но я не слишком беспокоюсь о накладных расходах для этого. Экземпляры узлов находятся в векторных узлах в структуре графа. Я надеюсь, что это проясняет мой вопрос больше?   -  person dj3000    schedule 29.01.2014

Ответы (1)


arrow_upward
1
arrow_downward

Вы ничего не упомянули о весе ребра.

Алгоритм Дейкстры работает, если у вас нет отрицательного веса ребра.

Алгоритм Беллмана-Форда работает, если у вас нет отрицательного цикла. Но вы также можете использовать алгоритм Беллмана-Форда, чтобы проверить, есть ли у вас отрицательный цикл.

Если это невесомый реберный граф, вы можете просто использовать BFS.

person noooooooob    schedule 28.01.2014