Suponha que tenhamos um gráfico ponderado não direcionado (com pesos não negativos). Vamos supor que todos os caminhos mais curtos em sejam únicos. Suponha que temos esses caminhos (sequências de arestas não ponderadas), mas não conhecemos o próprio G. Podemos produzir qualquer G que daria esses caminhos como o mais curto no tempo polinomial? A versão mais fraca: podemos decidir em tempo polinomial se esse G existe?G GGG
A condição óbvia necessária é a seguinte: para cada par de caminhos, sua interseção também é um caminho. Essa condição é suficiente?
Respostas:
Acabei de me deparar com essa pergunta antiga enquanto conduzia uma pesquisa acesa e, por acaso, recentemente obtive respostas neste artigo que eu também poderia compartilhar. Espero que a combinação de necromancia de tópicos e autopromoção seja perdoável.
A resposta é sim para ambos. O algoritmo de Mohammad definitivamente funciona, mas há um método mais rápido e direto que evita a necessidade de executar oráculos de separação cúbicos. Seja um gráfico auxiliar não ponderado, em que o peso de cada aresta é um número inteiro, indicando quantos dos caminhos tomados na entrada contêm essa aresta. Agora, considere a instância de fluxo multicomodidade capacitada por arestas sobre (interpretando pesos de arestas como capacidades) em que o objetivo é empurrar simultaneamente 1 unidade de fluxo entre cada par de nós. Obviamente, essa instância de fluxo MC pode ser satisfeita pressionando o fluxo de maneira natural pelos caminhos dados na entrada. Como se vê, pode-se provar que nossae ∈ E ( nH=(V,E,w′) e∈E H ( n(n2) H GG(n2) caminhos são caminhos mais curtos exclusivos em alguns se e somente se essa for a maneira exclusiva de satisfazer a instância de fluxo do MC. Podemos testar a singularidade configurando um LP cujas restrições são as usuais para a viabilidade do fluxo de MC mais uma certa função objetivo cuidadosamente escolhida, e os pesos de borda de um satisfatório podem ser extraídos do dual deste LP.G G
Essa condição às vezes é chamada de "consistência" (um conjunto de caminhos é consistente se a interseção de dois) for um subcaminho de cada um). Resulta do exposto que a consistência não é suficiente. Um dos dois contra-exemplos vinculados pelo menor é o seguinte sistema codificado por cores de quatro caminhos em seis nós:
Em outras palavras, não há como atribuir pesos às oito arestas representadas aqui, para que todos esses quatro caminhos sejam simultaneamente o caminho mais curto e único entre seus pontos de extremidade. No entanto, qualquer par deles se cruza em apenas um nó, portanto eles são consistentes (mesmo se os preenchermos com alguns caminhos adicionais da maneira correta para que no total). Existem infinitamente muitos contra-exemplos como este; veja o artigo para uma caracterização.(n2)
Três outros comentários rápidos sobre tudo isso:
fonte
Você pode escrever o problema como um LP, não é? Para quaisquer dois vértices u, ve qualquer caminho P de u até v, o peso de P é maior ou igual ao peso do caminho mais curto dado entre u e v. Todas essas são desigualdades lineares, e mesmo que haja exponencialmente, o problema de separação está em P (é apenas um problema de caminho mais curto para todos os pares). Portanto, você pode usar o algoritmo elipsóide para resolvê-lo.
fonte