Задать вопрос
Luffy1
@Luffy1
Student, Junior .NET programmer, C#, JS, HTML/CSS

Как найти наикратчайшие пути взвешенного орграфа, представленного матрицей инцидентности, используя алгоритм Дейкстры?

В интернете, к сожалению, я нашёл только алгоритм Дейкстры для матрицы смежности, но нигде нету алгоритма Дейкстры для матрицы инцидентности.
Моя матрица инцидентности (первый ряд цифр - номера вершин, то, что в {} - рёбра, всё остальное - вес; например, ребро {1;3} с весом 5 инцидентно вершине 3):
0 1 2 3 4 5 6 7
{0;1} 0 1 0 0 0 0 0 0
{0;2} 0 0 2 0 0 0 0 0
{1;2} 0 0 1 0 0 0 0 0
{1;3} 0 0 0 5 0 0 0 0
{1;4} 0 0 0 0 2 0 0 0
{2;3} 0 0 0 2 0 0 0 0
{2;4} 0 0 0 0 1 0 0 0
{2;5} 0 0 0 0 0 4 0 0
{3;4} 0 0 0 0 3 0 0 0
{3;5} 0 0 0 0 0 6 0 0
{3;6} 0 0 0 0 0 0 8 0
{4;5} 0 0 0 0 0 3 0 0
{4;6} 0 0 0 0 0 0 7 0
{5;6} 0 0 0 0 0 0 5 0
{5;7} 0 0 0 0 0 0 0 2
{6;7} 0 0 0 0 0 0 0 6
Для такого взвешенного орграфа:
656f4a7e9694c939162350.png
В прямоугольниках - вес ребра, а в кружках просто номера вершин, не вес.
Я пытаюсь написать алгоритм, который через алгоритм Дейкстры выведет наикратчайшие пути от введённой с клавиатуры вершины до всех других, то есть должно выводится вес пути и сам путь (вершины, через которые проходит этот путь).
Буду благодарен, если поможете с написанием алгоритма =)
На всякий: матрицу я представляю через вектор в коде:
vector<vector<int>> incidenceMatrix = {
	{0,1,0,0,0,0,0,0},
	{0,0,2,0,0,0,0,0},
	{0,0,1,0,0,0,0,0},
	{0,0,0,5,0,0,0,0},
	{0,0,0,0,2,0,0,0},
	{0,0,0,2,0,0,0,0},
	{0,0,0,0,1,0,0,0},
	{0,0,0,0,0,4,0,0},
	{0,0,0,0,3,0,0,0},
	{0,0,0,0,0,6,0,0},
	{0,0,0,0,0,0,8,0},
	{0,0,0,0,0,3,0,0},
	{0,0,0,0,0,0,7,0},
	{0,0,0,0,0,0,5,0},
	{0,0,0,0,0,0,0,2},
	{0,0,0,0,0,0,0,6},
};
  • Вопрос задан
  • 187 просмотров
Подписаться 1 Сложный 3 комментария
Решения вопроса 1
wataru
@wataru Куратор тега C++
Разработчик на С++, экс-олимпиадник.
Матрица инцидентности - абсолютно не эффективная структра представления графа практически для всех алгоритмов. Поэтому вы ее использование нигде найти и не можете.

Если уж такое задание и надо именно это делать, то берете любую реализацию алгоритма дейкстры, скажем, со списком смежности и ищите там то место, где происходит перебор всех соседних вершин. И переписываете его: Чтобы найти все соседние вершины, вам надо пройтись по списку всех ребер и, если в матрице в столбце текущей вершины стоит отрицательное число, то ищите в этой строке положительное число - и вот тот столбец это и есть соседняя вершина.

Кстати, у вас матрица инцидентности неправильная: должно быть по 2 числа в каждой строке. Обычно ставят -цену у начальной вершины и +цену у конечной.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
Alexandroppolus
@Alexandroppolus
кодир
Переделай матрицу инцидентности в матрицу смежности
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы