[HELP] Aidez moi a comprendre un programme

[invite23ed8df1]

Bonjour,

J'ai un projet en ISN (je suis en terminale). Ce projet consiste à réaliser un programme nommé "chemin le plus court" qui prend en entrée 2 sommets d'un graphe pondéré et grâce a un certain algorithme (notamment dijkstra) il nous donne le chemin le plus court liant ces 2 points. J'ai réussi a trouver un programme qui fonctionne parfaitement, j'ai implémenté mon graphe, cependant, je ne comprends vraiment pas le code et, malgré de nombreuses recherches, je suis toujours au point mort. J'aimerais que vous m'aidiez à mieux le comprendre.
Merci par avance.
Plus court chemin.docx
-----

[JPL]

Les codes doivent être postés dans une balise [Code]...[/Code] dans le corps du message.

[invite23ed8df1]

public class Graphe {

	//constructeurs
		private final List<Sommet> mesSommet;
		private final List<Arc> mesArc;
		//Construit un Graphe
		public Graphe(List<Sommet> sommet, List<Arc> arc) {
			this.mesSommet = sommet;
			this.mesArc = arc;
		}

		public List<Sommet> getSommet() {
			return mesSommet;
		}

		public List<Arc> getArc() {
			return mesArc;
		}	
	}

public class DijkstraAlgorithm {

	private final List<Sommet> noeux;
	private final List<Arc> arc;
	private Set<Sommet> noeuxfixe;
	private Set<Sommet> noeuxnonfixe;
	private Map<Sommet, Sommet> predecesseur;
	private Map<Sommet, Integer> distance;

	public DijkstraAlgorithm(Graphe graph) {
		// Crée une copie de la liste  pour pouvoir travailler avec le tableau si dessous.
		//ArrayList permet de prendre un argument.
		this.noeux = new ArrayList<Sommet>(graph.getSommet());
		this.arc = new ArrayList<Arc>(graph.getArc());
	}

	public void execute(Sommet source) {
		noeuxfixe = new HashSet<Sommet>();
		noeuxnonfixe = new HashSet<Sommet>();
		distance = new HashMap<Sommet, Integer>();
		predecesseur = new HashMap<Sommet, Sommet>();
		distance.put(source, 0);
		noeuxnonfixe.add(source);
		while (noeuxnonfixe.size() > 0) {
			Sommet noeux = getMinimum(noeuxnonfixe);
			noeuxfixe.add(noeux);
			noeuxnonfixe.remove(noeux);
			trouveDistMin(noeux);
		}
	}
//Procedure qui trouve la plus courte distance entre tous les noeux suivants
	private void trouveDistMin(Sommet noeux) {
		List<Sommet> noeuxadja = getVoisin(noeux);
		for (Sommet cible : noeuxadja) {
			if (getPlusCourteDistance(cible) > getPlusCourteDistance(noeux)+getDistance(noeux, cible)) {
				distance.put(cible, getPlusCourteDistance(noeux)+getDistance(noeux, cible));
				predecesseur.put(cible, noeux);
				noeuxnonfixe.add(cible);
			}
		}

	}
///Methode qui donne la distance entre deux noeux ou le poids.
	private int getDistance(Sommet noeux, Sommet cible) {
		for (Arc a : arc) {
			if (a.getSource().equals(noeux)&& a.getDestination().equals(cible)){
			return a.getWeight();
			}
		}
		throw new RuntimeException("cela n'arrive pas");
	}
///Crée une liste qui contient les noeux voisins d'un Noeux
	private List<Sommet> getVoisin(Sommet noeux) {
		List<Sommet> voisin = new ArrayList<Sommet>();
		for (Arc a : arc) {
			if (a.getSource().equals(noeux)&& !estfixe(a.getDestination())){
				voisin.add(a.getDestination());
			}
		}
		return voisin;
	}
///
	private Sommet getMinimum(Set<Sommet> sommet){
		Sommet minimum = null;
		for (Sommet s : sommet) {
			if (minimum == null) {
				minimum = s;
			} else {
				if (getPlusCourteDistance(s) < getPlusCourteDistance(minimum)) {
					minimum = s;
				}
			}
		}
		return minimum;
	}
//booléen qui dit si le sommet � �t� vu par l'algorithme.
	private boolean estfixe(Sommet sommet) {
		return noeuxfixe.contains(sommet);
	}
//Entier qui revnoi le plus petit poids
	private int getPlusCourteDistance(Sommet destination) {
		Integer d = distance.get(destination);
		if (d == null) {
			return Integer.MAX_VALUE;//plus grand entier machine=+infini.
		} else {
			return d;
		}
	}

	/*
	 * cette methode renvois le chemin depuis la source vers le noeux destination.
	 * NULL si il n'y a pas de chemin.
	 */
	public LinkedList<Sommet> getChemin(Sommet cible){
		LinkedList<Sommet> chemin = new LinkedList<Sommet>();
		Sommet etape = cible;
		// Check if a path exists
		if (predecesseur.get(etape) == null) {
			return null;
		}
		chemin.add(etape);
		while (predecesseur.get(etape) != null) {
			etape = predecesseur.get(etape);
			chemin.add(etape);
		}
		// Remet les noeux du chemin dans l'ordre
		Collections.reverse(chemin);
		return chemin;
	}

}
public class DijkstraFinal {

	/**
	 * @param args
	 */
	private List<Sommet> noeux;
	private List<Arc> arc;

[JPL]

J’avais dit dans une balise Code ! J’ai dû l’ajouter moi-même.

[A voir en vidéo sur Futura]

[danyvio]

L'algo de DIJKSTRA est bien décrit et corrigé dans le livre de ROSEAUX "Exercices et problèmes de recherche opérationnelle".
J'aime cet algo que j'avais (re)trouvé tout seul comme un grand en imaginant le graphe comme une pelote de fils noués, dont j'écartais deux nœuds, pour calculer le fil tendu qui était intuitivement le plus court chemin entre les deux nœuds.

Mais DIJKSTRA avait l'antériorité de ma "découverte" et mon nom est resté dans les oubliettes de la RO