Como encontrar o caminho mais curto de algum vértice no conjunto para definir

Se eu tiver um gráfico , um subconjunto de vértices e um segundo conjunto de vértices , qual é a melhor maneira de encontrar o caminho mais curto conectando o dois conjuntos? Ou seja, estamos procurando um caminho mais curto entre todos caminhos de - . Também podemos assumir que todos os pesos de borda são positivos. $G=(V,E)$ $S \subset V$ $S' \subset (V\setminus S)$ $S$ $S'$

Aqui está como eu tenho abordado esse problema até agora:

Eu já tenho as informações da matriz de distância para o gráfico que foram calculadas aplicando o algoritmo de Floyd-Warshall em uma operação anterior. $(d)$ $G$

Eu, então, itere sobre todos os vértices em para cada vértice em e encontro o par com o menor valor na matriz . $S$ $S'$ $(s_1,s_2)$ $d$

O algoritmo de Dijkstra é então usado para calcular o caminho mais curto entre $s_1$ e $s_2$ , portanto, conectar o vértice define $S$ e $S'$ .

Existe uma maneira mais eficiente de alcançar esse mesmo resultado?

algorithms graphs optimization shortest-path guskenny83
fonte

Se todos os comprimentos das arestas não forem negativos, isso poderá ser resolvido no tempo $O(|E| \lg |V|)$ usando uma única invocação do algoritmo de Dijkstra.

Vamos modificar um pouco o gráfico adicionando um novo vértice $s$ . Além disso, adicionar uma aresta de comprimento a partir de 0 $s$ para cada vértice em $S$ .

Em seguida, execute o algoritmo de Dijkstra, iniciando no vértice de origem . O algoritmo de Dijkstra irá calcular para você a distância para cada outro vértice , ou seja, ele vai calcular para todo . Observe que será exatamente o comprimento do caminho mais curto de algum vértice em até o vértice . $s$ $s$ $v$ $d(s,v)$ $v \in V$ $d(s,v)$ $S$ $v$

Por fim, calcule . Este será o comprimento do caminho mais curto, de algum vértice em até algum vértice em . Essa é a sua resposta. $\min \{ d(s,v) : v \in S' \}$ $S$ $S'$

Não há necessidade de executar o Floyd-Warshall.

Se você pode ter arestas negativas, isso pode ser feito no tempo . Simplesmente substitua o algoritmo de Dijkstra pelo algoritmo de Bellman-Ford. $O(|V| \cdot |E|)$

DW
fonte

Você pode até salvar o cálculo do mínimo adicionando outro novo vértice para . (Note-se que o tempo de execução ligada assume , que é razoável; provavelmente pode ser assumida a ser conectado aqui.)

S^{'}

$S'$

| E | \in Ω (| V |)

$|E| \in \Omega(|V|)$

G

$G$

Raphael

obrigado pela sua resposta, isso faz muito sentido. Em relação ao seu ponto de não precisar executar o Floyd-Warshall, se eu já executei o floyd-warshall para outra coisa e já tenho essa informação disponível, seria mais rápido fazer uma pesquisa no gráfico de distância? ou não? porque precisamos executar o dijkstra de qualquer maneira, é mais rápido usar o método de vértice fictício?

precisa saber é o seguinte

@ guskenny83, depende. Se você já está executando o Floyd-Warshall, encontrar o caminho mais curto usando sua saída levará tempo para procurar todas as entradas na matriz para . Isso pode ser mais lento ou mais rápido do que executar o algoritmo de Dijkstra, dependendo do tamanho dos conjuntos e do gráfico. Para gráficos esparsos e conjuntos grandes , será mais lento no pior dos casos.

O (| S | \cdot | S^{'} |)

$O(|S| \cdot |S'|)$

d [u, v]

$d[u,v]$

u \in S, v \in S^{'}

$u \in S, v \in S'$

S, S^{'}

$S,S'$

S, S^{'}

$S,S'$

Como encontrar o caminho mais curto de algum vértice no conjunto para definir

Respostas: