public class GrapheValue extends Graphe{

    double[] w ;// tableau contenant les longueurs des arcs

    //constructeur à partir des arcs
    GrapheValue(int NS, int[] orig, int[] extr, double[] w){
	super(NS,orig,extr);
	this.w= w;
	
    }

    //affiche le graphe
    void affiche(){
	super.affiche();
	System.out.print("  w  |");
	for (int i=0; i<NA;i++){
	    System.out.print(w[i]+"|");
	}
	System.out.println();
    }

    //algorithme de Ford
    void ford(int s){
	initDistance(s);
	initPeres();
	boolean continuer = true;
	while(continuer){
	    continuer = false;
	    for(int i =0;i<NA;i++){
		if((distance[orig[i]-1]+w[i])<distance[extr[i]-1]){
		    distance[extr[i]-1]= distance[orig[i]-1]+w[i];
		    peres[extr[i]-1]=orig[i];
		    continuer = true;
		}
	    }
	}
    }

    //affiche les distances à un sommet
    void afficheDistance(int s){
	ford(s);
	System.out.println("Les distances au sommet "+ s + " sont pour les sommets :");
	System.out.println();
	for(int i =0;i<NS;i++){
	    System.out.println((i+1)+" : "+ distance[i]);
	    afficheChemin(i+1);
	    System.out.println();
	}
	System.out.println();
    }

    public static void main(String[] arg){
	System.out.println("Graphe valué du TD");
	int [] orig={1,2,1,4,2,5,4};
	int [] extr={2,3,4,2,5,3,5};
	double[] w= {4,1,1,2,1,3,2};
	GrapheValue g = new GrapheValue(5,orig,extr,w);
	g.affiche();
	System.out.println();
	g.afficheDistance(1);
    }

}