Я хочу найти общее количество всех минимальных путей между s и t через v в графе, где s, t и v являются узлами графа, используя алгоритм Флойда Уоршалла. Заранее спасибо за ваши ответы.
Как найти общее количество всех минимальных путей между s и t через v в графе?
comment
Привет, Добро пожаловать в переполнение стека. Перейдите по ссылке Как задать вопрос, чтобы получить более подробную информацию о том, как задать вопрос и соответствующим образом обновить свой вопрос.
- person Jeroen Heier schedule 20.07.2017
Ответы (1)
найдите количество кратчайших путей между s и v с помощью floyd-warshall, затем найдите все кратчайшие пути от v до t, а затем умножьте результат. например, если есть 3 кратчайших пути между s и v, 2 кратчайших пути из v в t, то существует 6 кратчайших путей из s в t через v.
person
pooya
schedule
20.07.2017
например, если у меня есть ориентированный полный граф, когда мне нужно вычислить количество кратчайших путей с v = 0, i = 1 и j = 2, прежде чем i будет увеличено, у меня есть минимум 98 путей? инт я, дж, в; инт рис = 0; for (v = 0; v ‹ n_nodi; v++) { for (i = 0; i ‹ n_nodi; i++) { for (j = 0; j ‹ n_nodi; j++) { if (i != j && i != v && j != v) { ris += (graph[i][v] * graph[v][j]); } } } } большое спасибо за доступность
- person Luca Valentini; 21.07.2017
вы можете найти информацию о реализации floyd-warshall на желаемом вами языке, а затем, как я уже сказал, вычислить количество путей между s, v и v, t, а затем умножить их.
- person pooya; 21.07.2017
