Самый короткий путь и алгоритм Дейкстры

Я не могу найти никаких указаний на этот вопрос в Интернете, и, поскольку я на экзамене, у меня заканчивается время, вопрос довольно прост, и любое объяснение будет приветствовать (хотя простой да или нет).Самый короткий путь и алгоритм Дейкстры

Для алгоритма Дейкстры должен быть сильно связан граф? То есть каждая вершина может быть достигнута из любой другой вершины? Или возможно ли иметь недостижимые вершины и, следовательно, вы должны начать с другого узла с помощью алгоритма?

Чтобы добавить к этому вопросу: Алгоритм Дейкстры применяется только к неориентированным графам? поскольку все примеры из моего учебника относятся к неориентированным ребрам.

источник

2016-12-11 JmanxC

«Я на экзамене, у меня заканчивается время» ... разве это не обман? –

@RobMurray Возможно, он имеет в виду, что он на экзаменационной неделе, а не настоящий экзамен прямо сейчас? – technokrat

Алгоритм Дейкстры применяется на графиках DIRECTED. –

Неориентированный граф в основном ориентированный граф, но с двунаправленными соединениями. Так что нет, Dijkstra's может также применяться к ориентированным графам.

Для слабосвязанных графов это зависит.

Скажите, что у вас есть график A и график B. Вы можете перейти от A в B, но не от B до A. Если вы начинаете с A и хотите найти кратчайший путь в B, то Dijkstra будет работать. Но, естественно, вы не можете начать с B и попытаться найти путь к узлу в A.

источник

2016-12-11 23:32:17 technokrat

Спасибо. Я не хотел считать, что алгоритм работает только на сильных связных и двунаправленных графиках. – JmanxC

@JmanxC В будущем, всякий раз, когда вы путаетесь с подобными вещами, хорошей практикой является составление графика и переход на то, как алгоритм будет работать на нем. Это требует немного умственных усилий, но обычно дает результаты быстрее, чем поиск в Интернете для вашего конкретного случая. – technokrat

Самый короткий путь и алгоритм Дейкстры

ответ

Смежные вопросы