Peut Dijkstra Unique Source de plus court Chemin Algorithme de détecter une boucle infinie dans un graphique?
Alors je suis venu à ce beau problème qui vous demande d'écrire un programme qui détecte si un infini négatif le plus court chemin d'accès n'existe dans un graphe orienté. (Peut également être considéré comme constatation de l'existence d'un "cercle vicieux" existe dans le graphe). Voici un lien pour le problème:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=499
J'ai réussi à résoudre le problème en exécutant Bellman Ford Algorithme à deux reprises, en commençant par n'importe quelle source dans le graphique. La deuxième fois que je lance l'algorithme, - je vérifier si un nœud peut être détendu. Si oui, alors il est certainement l'un cycle négatif dans le graphique. Ci-dessous mon code C++:
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
int test;
cin>>test;
for(int T=0; T<test; T++)
{
int node, E;
cin>>node>>E;
int **edge= new int *[E];
for(int i=0; i<E; i++)
{
edge[i]= new int [3];
cin>>edge[i][0]>>edge[i][1]>>edge[i][2];
}
int *d= new int [node];
bool possible=false;
for(int i=0; i<node;i++)
{
d[i]= 999999999;
}
d[node-1]=0;
for(int i=0; i<node-1; i++)
{
for(int j=0; j<E; j++)
{
if(d[edge[j][1]]>d[edge[j][0]]+edge[j][2])
d[edge[j][1]]=d[edge[j][0]]+edge[j][2];
}
}
//time to judge!
for(int i=0; i<node-1; i++)
{
for(int j=0; j<E; j++)
{
if(d[edge[j][1]]>d[edge[j][0]]+edge[j][2])
{
possible=true;
break;
}
}
if(possible)
break;
}
if(possible)
cout<<"possible"<<endl;
else
cout<<"not possible"<<endl;
}
}Un professeur m'a dit une fois que Dijkstra plus court chemin algorithme ne peut pas trouver un tel cycle négatif, mais il ne la justifie pas. En fait je doute de cette affirmation.
Ma question est, peut Dijktstra unique source de plus court chemin algorithme de détecter que le cycle négatif?
Bien sûr, je peux essayer de Dijkstra et de vérifier si elle fonctionne, mais j'ai été ravie de partager cette idée avec vous.
- ce que vous entendez par l'infini?
- Désolé, je pense que le bon terme est "cycle négatif". Dans un pesé graphique, un cycle négatif est un cycle dont la somme des pondérations de bords est négatif.
Vous devez vous connecter pour publier un commentaire.
Vous avez mal compris votre professeur: il doit avoir dit que l'algorithme de Dijkstra ne fonctionnera pas si il y a un négatif cycle dans le graphe. Positif cycles sont autorisés.
La raison pour laquelle l'algorithme ne fonctionne pas sur les graphiques avec des cycles négatifs, c'est que le chemin le plus court dans de tels graphiques n'est pas défini: une fois que vous obtenez à un cycle négatif, vous pouvez diminuer le coût de votre "chemin le plus court" aussi bas que vous le souhaitez en suivant le cycle négatif à plusieurs reprises.
Prenons l'exemple ci-dessus: vous commencez au sommet
Start, et d'arriver àAavec le coût de1. Puis vous allez àBavec le coût total de-1, àCavec le total de-4, et maintenant vous pouvez revenir àAavec le coût total de zéro. Par l'extension de la séquenceStart-A-B-C-A-B-C-A-B-C-...-Finishvous pouvez réduire le coût d'un chemin d'accès à partir deStartàFinishpour un aussi petit nombre négatif comme vous le souhaitez.Noter que le cycle négatif restriction s'applique à toutes les algorithmes pour trouver un plus court chemin dans un graphe. La restriction sur l'algorithme de Dijkstra est encore plus forte: elle interdit toute négative bords.
Il est certainement possible de modifier l'algorithme de Dijkstra pour détecter des cycles négatifs, mais il n'y a pas de point à le faire, parce que vous avez une forte restriction de ne pas avoir de négatif bords.
Finish. C'est pour 2 raisons: une Fois qu'un nœud est marqué que la visite à l'aide de Dijkstra, il n'est pas visité de nouveau; Voir cette réponse pour une explication. La prochaine raison est parce que la distance C est -3 puis la prochaine option viable après la visite C estFinishparce que-3 + 1 < -3 + 4Pas d'algorithme ni Dijkstra, ni de Bellman-Ford, ni de Floyd-Warshall travailler sur des graphes avec des cycle négatif mais les deux derniers peuvent détecter un alors que Dijkstra est pas parce que Dijkstra est gourmand alors que d'autres l'utilisation de la programmation dynamique. En outre Dijkstra ne fonctionne pas avec le poids est négatif, même sans des cycles négatifs.