J'ai un graphique qui est de poids égal. Comment puis-je trouver le chemin le plus court?
Nous pouvons utiliser algorithme de dijkstra et trouver le chemin le plus court. Je pense que la backtracking sera utilisée dans ce cas. Mais y a-t-il une autre façon de trouver le chemin le plus court de manière optimale car le graphique est de poids égal?
4 Réponses :
BFS est le meilleur moyen d'obtenir le chemin le plus court d'un nœud à un autre ... Il trouve d'abord tous les nœuds à distance 1 puis 2 et ainsi de suite sur
+1 Le plus simple et le plus rapide. Bien que cela puisse être considéré comme des connaissances communes (et Google est votre ami), vous pouvez ajouter que BFS signifie la première recherche de la largeur :)
est passé à travers le BFS et pourrait le comprendre rapidement. Merci cela m'a aidé. J'ai référé cours.fr.illinois.edu/cs473/sp2011/Lectus/ 03_Class.pdf
Je pense que l'algorithme BFS est préférable pour le graphe avec des poids égaux pour résoudre le chemin le plus court. Je pense que BFS est également le meilleur algorithme dans un graphique satisfaire l'inégalité de triangle, comme un graphique plane.
Je ne comprends pas tout à fait ce que vous essayez de dire mais de trouver le plus court chemin comme algorithme de Dijkstra, recherchez une * (prononcé une étoile). C'est un algorithme similaire que celui-ci adapte une heuristique à réduire le nombre de chèques dont il est nécessaire. Dijkstra est presque comme un * avec une heuristique de zéro qui est loin de la vraie heuristique. Plus vous pouvez prédire la heuristique l'algorithme plus rapide.
Vous pouvez également utiliser des algorithmes FLOYD> Floyd-Warshall Strong> pour calculer les chemins les plus courts entre chaque paire de nœuds dans le graphique. Si votre graphique est petit et que vous ferez beaucoup d'interrogation, c'est la voie à suivre. L'algorithme est assez simple:
public static void floydwarshall(int[][] graph){
for(int k=0; k<graph.length; k++){
for(int i=0; i<graph.length; i++){
for(int j=0; j<graph.length; j++){
graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
}
}
}
}