Обновление матрицы путей в графе

У меня есть эта матрица, которая содержит путь между вершинами. Например, для 4 вершин у нас есть такая матрица:

0 0 1 1

1 0 1 1

0 0 0 1

0 0 0 0

Это показывает нам, что у нас есть путь между (1,3) и (1,4) и (2,1) и (2,3) и (2,4) и (3,4).

Вход моей проблемы - это новый путь между двумя вершинами, а выход - обновление этой матрицы.

Например :

Вход:(3,2)

Выход:

1 1 1 1

1 1 1 1

1 1 1 1

0 0 0 0

Я хочу сделать это в таком порядке: O(V^2)


java graph algorithm np
person ali khorshidi rozbahani    schedule 22.01.2016    source источник
comment
Если вы добавите только один новый путь, почему 6 значений изменились с 0 на 1? Например. почему вывод показывает путь (1,1)?   -  person Andreas    schedule 23.01.2016
comment
@Андреас, потому что мы можем перейти от 1 к 3, а затем от 3 к 2 и обратно к 1 от 2. в чем проблема ?   -  person ali khorshidi rozbahani    schedule 23.01.2016
comment
Хорошо, теперь понял, спасибо. Теперь, что вы пробовали до сих пор? (см. пункт 3 в разделе О каких темах я могу здесь спросить?)   -  person Andreas    schedule 23.01.2016

Ответы (1)


arrow_upward
1
arrow_downward

N = номер вершины.

У вас есть новое преимущество: введите (A, B).

1 Затем вы перебираете B: для каждого существующего ребра (B,X) вы получаете (возможно новое) ребро (A,X) => si N операций

2 То же самое с A: для каждого существующего ребра (Y,A) вы получаете (возможно новое) ребро (Y,B) => si N операций

Вы делаете то же самое с X и Y (максимум 2 N).

3 Для каждых (Y,A) и (B,X) вы добавляете (Y,X), то есть NxN операций.

So it is O(N^2)

person guillaume girod-vitouchkina    schedule 22.01.2016