Encontre todos os gráficos especiais que podem ser reduzidos ao gráfico de caminhos mais curtos

Eu tenho um gráfico ponderado direcionado . Sempre existe uma aresta de um vértice para outro , o peso pode ser infinito positivo e não existe ciclo negativo. $G = (V, E, W)$ $i$ $j$ $w(i,j)$

Uma execução de alguns algoritmos encontrará os comprimentos (pesos somados) dos caminhos mais curtos entre todos os pares de vértices, embora não retorne detalhes dos próprios caminhos. Por exemplo, o algoritmo de Floyd-Warshall é direto e funciona. Vamos denotar o resultado por . $G' = (V, E, W')$

Em , é possível que para uma aresta de a , . Vamos fazer de outro gráfico cujo elemento seja igual a exceto . Portanto, sabemos que a execução de um algoritmo de caminhos mais curtos em dará . $G'$ $i$ $j$ $w'(i,j) = w'(i, k_0) + w'(k_0, k_1) + \dots + w'(k_n, j)$ $G'$ $G''$ $G'$ $w''(i,j) = \infty \neq w'(i,j)$ $G''$ $G'$

Então dado um $G'$ 'eu gostaria de encontrar todos os gráficos como $G''$ , tal que para todo $i$ e $j$ , $w''(i,j) \in \{ w'(i,j), \infty\}$ e $G''$ pode ser reduzido a $G'$ através de um algoritmo de caminhos mais curtos.

Espero que minha pergunta seja clara ... Não sei se já existe um algoritmo para isso, alguém tem alguma ideia?

algorithms graph-theory SoftTimur
fonte

Eu não entendo o que você está recebendo aqui. O que é , o gráfico que consiste nos caminhos mais curtos? Ou um gráfico com arestas de a com o peso do caminho mais curto de a em ?

G^{'}

$G'$

i

$i$

j

$j$

i

$i$

j

$j$

G

$G$

Raphael

@Raphael, G' é o segundo caso (mais curto gráfico caminho), mas eu não sei o que é G "?

Ah, eu acredito que eu começar a ver a pergunta: Dada uma árvore , enumerar todos os gráficos cuja árvore de caminho mais curto é . Isso está correto? Ainda estou um pouco confuso com as restrições ao você define. Se minha interpretação estiver correta, observe o seguinte: existem infinitamente muitos desses gráficos.

T

$T$

T

$T$

G^{″}

$G''$

Raphael

Você quer dizer: todo é obtido removendo uma ou mais arestas de , sujeito ao critério de que as distâncias entre todos os vértices permanecem as mesmas? Ou as bordas também podem ser adicionadas ?

G^{″}

$G''$

G

$G$

reinierpost

Encontre todos os gráficos especiais que podem ser reduzidos ao gráfico de caminhos mais curtos

Respostas: