Problème du sac à dos – Algorithme en Python (knapsack problem)

Le problème du sac à dos en algorithmique (et son implémentation python) est intéressant et fait parti du programme de Sciences numériques et informatique de première.

Ce problème illustre les algorithmes gloutons qui énumèrent toutes les possibilités de résolution d’un problème pour trouver la meilleure solution.

Le problème du sac à dos algorithme python est un problème d’optimisation, c’est à dire une fonction que l’on doit maximiser ou minimiser et des contraintes qu’il faut satisfaire.

Le problème du sac à dos – algorithme Python

Pour un sac à dos de capacité maximale de P et N articles chacun avec son propre poids et une valeur définie, jetez les articles à l’intérieur du sac à dos de telle sorte que le contenu final ait la valeur maximale.

Exemple d’énoncé :

  • Capacité maximum du sac à dos : 11 unités
  • Nombre d’objet : 5
  • Valeurs des objets : {10,50,20,30,60}
  • Poids des objets : {1,5,3,2,4}

Quelles est la valeur maximum qu’il est possible de mettre dans le sac à dos en considérant la contrainte de capacité maximum du sac qui est de 11 ?

Algorithme glouton python

Une solution efficace consiste à utiliser un algorithme glouton. L’idée est de calculer le rapport valeur / poids pour chaque objet et de trier l’objet sur la base de ce rapport calculé .

On prends l’objet avec le ratio le plus élevé et on ajoute jusqu’à ce qu’on ne puisse plus en ajouter.

En version fractionnaire il est possible d’ajouter des fractions d’article au sac à dos.

Implémentation du problème du sac à dos Python – version non fractionnaire

Voici une implémentation du problème du sac à dos python en version non fractionnaire, c’est à dire qu’on ne peut pas ajouter de fraction d’un objet dans le sac. Seul des objets entiers peuvent être ajoutés.

class ObjetSac: 
    def __init__(self, poids, valeur, indice): 
        self.indice = indice         
        self.poids = poids 
        self.valeur = valeur
        self.rapport = valeur // poids 
  #Fonction pour la comparaison entre deux ObjetSac
  #On compare le rapport calculé pour les trier
    def __lt__(self, other): 
        return self.rapport < other.rapport 
  

def getValeurMax(poids, valeurs, capacite): 
        tableauTrie = [] 
        for i in range(len(poids)): 
            tableauTrie.append(ObjetSac(poids[i], valeurs[i], i)) 
  
        #Trier les éléments du sac par leur rapport
        tableauTrie.sort(reverse = True) 
  
        compteurValeur = 0
        for objet in tableauTrie: 
            poidsCourant = int(objet.poids) 
            valeurCourante = int(objet.valeur) 
            if capacite - poidsCourant >= 0: 
                #on ajoute l'objet dans le sac
                #On soustrait la capacité
                capacite -= poidsCourant 
                compteurValeur += valeurCourante
                #On ajoute la valeur dans le sac 
        return compteurValeur 


poids = [1,5,3,2,4] 
valeurs = [10,50,20,30,60] 
capacite = 11
valeurMax = getValeurMax(poids, valeurs, capacite) 
print("Valeur maxi dans le sac à dos =", valeurMax) 

Le résultat obtenu est le suivant :

py sacados.py 
Valeur maxi dans le sac à dos = 120

Implémentation du problème du sac à dos python – version fractionnaire

En version fractionnaire de l’agorithme du sac à dos python on peut ajouter des fractions d’objet au sac à dos.

class ObjetSac: 
    def __init__(self, poids, valeur, indice): 
        self.indice = indice         
        self.poids = poids 
        self.valeur = valeur
        self.rapport = valeur // poids 
  #Fonction pour la comparaison entre deux ObjetSac
  #On compare le rapport calculé pour les trier
    def __lt__(self, other): 
        return self.rapport < other.rapport 
  

def getValeurMax(poids, valeurs, capacite): 
        tableauTrie = [] 
        for i in range(len(poids)): 
            tableauTrie.append(ObjetSac(poids[i], valeurs[i], i)) 
  
        #Trier les éléments du sac par leur rapport
        tableauTrie.sort(reverse = True) 
  
        compteurValeur = 0
        for objet in tableauTrie: 
            poidsCourant = int(objet.poids) 
            valeurCourante = int(objet.valeur) 
            if capacite - poidsCourant >= 0: 
                #on ajoute l'objet dans le sac
                #On soustrait la capacité
                capacite -= poidsCourant 
                compteurValeur += valeurCourante
                #On ajoute la valeur dans le sac 
            else: 
                fraction = capacite / poidsCourant 
                compteurValeur += valeurCourante * fraction 
                capacite = int(capacite - (poidsCourant * fraction)) 
                break
        return compteurValeur 


poids = [1,5,3,2,4] 
valeurs = [10,50,20,30,60] 
capacite = 11
valeurMax = getValeurMax(poids, valeurs, capacite) 
print("Valeur maxi dans le sac à dos =", valeurMax) 

Le résultat obtenu est le suivant :

py sacados.py 
Valeur maxi dans le sac à dos = 140.0

Liens internes algorithme python :

https://128mots.com/index.php/category/python/

https://128mots.com/index.php/2021/01/21/algorithme-glouton-python/
https://128mots.com/index.php/2021/01/19/levenshtein-python/
https://128mots.com/index.php/2021/01/13/algorithme-tri-quantique/

Liens externes algorithme python :

http://math.univ-lyon1.fr/irem/IMG/pdf/monnaie.pdf

http://www.dil.univ-mrs.fr/~gcolas/algo-licence/slides/gloutons.pdf

Construire une application décentralisée full-stack pas à pas (Ethereum Blockchain Dapp) en plus de 128 mots – Partie 3

Cet article fait suite aux deux premiers articles sur le sujet :

Les 2 premiers articles permettent de mieux comprendre le concept de blockchain et d’application décentralisée.

Création du projet

On crée un répertoire pour le projet d’application de vote sur des chansons.

mkdir vote-chanson-dapp

Pour accélérer le développement on va utiliser une “truffle box” : https://www.trufflesuite.com/boxes

C’est en quelques sorte un modèle, un canevas d’application qui vous permet de vous focaliser sur la Dapp en ayant une structure déjà créée.

Je vais baser mon explication sur la pet-shop box disponible ici : https://www.trufflesuite.com/tutorials/pet-shop. C’est un des premiers tutos de truffle pour créer une Dapp.

Cette truffle box comprend la structure de base du projet ainsi que le code de l’interface utilisateur.

Utilisez la commande truffle unbox :

truffle unbox pet-shop

Pour rappel l’installation de truffle est possible via la commande :

npm install -g truffle

Si vous ouvrez le dossier vote-chason-dapp avec vscode vous obtenez alors l’arborescence suivante :

Arborescence du projet de l’application Dapp exemple (basée sur pet-shop de truffle)
  • contract : stockage du smart contract de l’application
  • migration : Les migrations permettent de transférer les smarts contracts vers la blockchain Ethereum (en local test ou mainnet). Les migrations permettent également de relier des smart contrats avec d’autres smarts contracts et de les initialiser.
  • node_modules : Le dossier node_modules contient les bibliothèques téléchargées depuis npm.
  • src : Répertoire de l’application front-end (client)
  • test : Stockage des tests pour l’application
  • truffle-config.js : fichier Javascript qui peut exécuter tout code nécessaire pour créer votre configuration.

Création du smart contract

Pour rappel nous développons une application qui permet d’élire la chanson préférée des électeurs.

Nous allons créer dans un premier temps la partie qui permet de créer un vote pour la meilleure chanson basée sur 3 chansons éligibles.

Le contrat écrit en solidity est le suivant :

contract TopChanson {
        struct Chanson {
        uint identifiant;
        string titre;
        uint compteur;
    }
    uint public compteurDeChansons;
    mapping(uint => Chanson) public chansons;

    function ajouterChansonElligible (string memory nomChanson) private {
        compteurDeChansons ++;
        chansons[compteurDeChansons] = Chanson(compteurDeChansons, nomChanson, 0);
    }

    function TopChansons() public {
        ajouterChansonElligible("Au clair de la lune");
        ajouterChansonElligible("Maman les p'tits bateaux");
        ajouterChansonElligible("Ah ! Les crocodiles");
    }

}

A noter l’utilisation de “mapping(uint => Chanson) public chansons;”

A lire : https://solidity.readthedocs.io/en/v0.6.6/types.html#mapping-types

Cette structure de donnée va nous permettre de stocker les titres des chansons éligibles à la façon d’une table de hachage. C’est à dire un tableau qui prend pour clé d’accès dans notre cas un uint qui est l’identifiant de la chanson et permet de récupérer la valeur qui est un type Chanson structuré.

Le type Chanson est structuré, voir la documentation solidity : https://solidity.readthedocs.io/en/v0.6.6/types.html#structs

Ici il y a un cas particulier sur la fonction ajouterChansonElligible, elle prends en argument le nom de la chanson qui est une chaine de caractère STRING. Si on ajoute pas le mot clé “memory” on obtient l’erreur suivante:

TypeError: Data location must be “storage” or “memory” for parameter in function, but none was given.

Pour les paramètres de fonction et les variables de retour, l’emplacement des données doit être explicité pour toutes les variables de type (struct, mapping, string).

La migration du contrat s’effectue via la commande :

truffle migrate --reset

On obtient alors :

Compiling your contracts...
===========================
> Compiling ./contracts/Migrations.sol
> Compiling ./contracts/TopChanson.sol

A suivre …

Construire une application décentralisée full-stack pas à pas (Ethereum Blockchain Dapp) en plus de 128 mots – Partie 2

Cet article fait suite au premier article sur le sujet : https://128mots.com/index.php/2020/03/30/construire-une-application-decentralisee-full-stack-pas-a-pas-ethereum-blockchain-dapp-en-plus-de-128-mots-partie-1/

Exemple d’application décentralisée (Dapp) de vote

L’utilisateur de l’application décentralisée a besoin d’un portefeuille qui contient des Ether. Comme indiqué dans le premier article il est possible de se créer facilement un wallet sur https://metamask.io/.

Dans un premier temps nous utiliserons le réseau ropsten. Ropsten Ethereum, également connu sous le nom de «Ethereum Testnet», est comme son nom l’indique, un réseau de test qui exécute le même protocole qu’Ethereum et est utilisé à des fins de test avant de se déployer sur le réseau principal (Mainnet). https://ropsten.etherscan.io/

L’utilisation va nous permettre de créer et d’utiliser gratuitement notre application avant d’éventuellement la diffuser sur le réseau principal d’Ethereum.

Lorsque l’utilisateur se connecte à notre application et au réseau il envoie son vote et doit payer quelques frais via son portefeuille afin d’écrire sa transaction dans la Blockchain (Appelé “Gas”, ce terme se réfère aux frais pour mener à bien une transaction ou exécuter un contrat sur la blockchain Ethereum).

Architecture de l’application Dapp

L’architecture de l’application se compose d’un front-end qui sera en HTML et Javascript. Ce Frontend dialoguera directement avec la blockchain ethereum local que nous installerons.

Architecture de l’application DAPP

Comme indiqué dans le premier article les règles métier et la logique seront codées dans un Smart Contract. Le Smart Contract est rédigé avec le langage de programmation solidity : https://solidity.readthedocs.io

Création du Front-End

Le front-end sera simple il permet d’afficher le résultat du vote pour sa chanson préférée sous forme d’une liste et de choisir dans une liste déroulante la chanson pour laquelle on souhaite voter.

Vérifier l’installation de node

node -v

Si node n’est pas installé vous pouvez vous référer à mon article sur angular : https://128mots.com/index.php/2020/02/27/angular-en-plus-de-128-mots-partie-1/

Installation de Metamask : il s’agit d’installer https://metamask.io/ en tant qu’extension de votre navigateur

Installation du framework truffle : Truffle est un environnement de développement, un cadre de test et un pipeline d’actifs pour Ethereum, visant à vous faciliter la vie en tant que développeur Ethereum. Il fournit des outils qui nous permettent d’écrire des contacts intelligents avec le langage de programmation Solidity.

Il sera également utilisé pour développer le front-end de l’application.

npm install -g truffle

Installation de Ganache :

Ganache est une blockchain personnelle pour le développement Ethereum que vous pouvez utiliser pour déployer des contrats, développer vos applications et exécuter des tests.

https://www.trufflesuite.com/ganache

Cela va vous permettre d’avoir une blockchain locale avec 10 comptes qui sont alimenté avec des faux Ether.

J’ai démarré l’application et j’ai cliqué sur Quick Start

On voit s’afficher les différents comptes de notre blockchain locale.

ANGULAR en moins de 128 mots – TypeScript – Angular Partie 8

Cet article fait suite aux sept premiers sur le sujet ANGULAR et porte sur le langage TypeScript :

Templates et interpolation

L’interpolation est l’incorporation d’expressions dans du texte balisé. Par défaut, l’interpolation utilise comme délimiteur les doubles accolades, {{ et }}.

<h3>Client n° : {{ numeroClient }}</h3>

Exemple de directive avec itération :

<li *ngFor="let client of listeClients">{{client.nom}}</li>

Services :

Les services permettent de découpler le composant de l’appel à un service, ils sont ainsi réutilisables.

ng generate service client
import { Injectable } from '@angular/core';

@Injectable({
  providedIn: 'root',
})
export class ClientService {

  constructor() { }

}

La logique est alors découplée du service qui est injectable via l’injection de dépendance.

Injection de dépendance

Exemple d’injection de la dépendance ClientService dans un composant ClientComponent

import { Component, OnInit } from '@angular/core';

import { Hero } from '../hero';
import { HeroService } from '../hero.service';
import { MessageService } from '../message.service';

@Component({
  selector: 'app-heroes',
  templateUrl: './heroes.component.html',
  styleUrls: ['./heroes.component.css']
})
export class ClientComponent implements OnInit {

...

  getClients(): void {
    this.clientService.getClients();
  }
}

Typescript Getter Setter ANGULAR

Cet article fait suite aux six premiers sur le sujet ANGULAR Typescript Getter Setter et porte sur le langage TypeScript :

Constructeur :

Le constructeur est la méthode appelée à la création de l’instance d’un objet

class Point {
    x: number;
    y: number;

    constructor(x: number, y: number) {
        this.x = x;
        this.y = y;
    }
    ajouter(point: Point) {
        return new Point(this.x + point.x, this.y + point.y);
    }
}

var p1 = new Point(30, 5);
var p2 = new Point(14, 21);
var p3 = p1.ajouter(p2);

Paramètre optionnel :

Si un paramètre est déclaré optionnel alors tous les paramètres déclarés à sa droite sont optionnels. Exemple du paramètre name dans le constructeur.

class Point {
    x: number;
    y: number;
    name: string;

    constructor(x: number, y: number, name?:string) {
        this.x = x;
        this.y = y;
        this.name = name;
    }
}

Visibilité :

Par défaut la visibilité du paramètre est publique, on peut utiliser des “access modifier” pour la modifier.

class Point {
    private x: number;

Les modificateurs d’accès peuvent être positionnés sur les méthodes, les variables et les propriétés.

class Point {
...
     private ajouter(point: Point) {
        return new Point(this.x + point.x, this.y + point.y);
    }
}
class Point {
...
    constructor(private x: number, private y: number) {
...

L’ajout d’un modificateur d’accès (public / privé / protégé / en lecture seule) à un paramètre constructeur affectera automatiquement ce paramètre à un champ du même nom.

Typescript getter setter :

TypeScript prend en charge les getters / setters comme moyen d’intercepter les accès à un membre d’un objet.

Cela permet d’avoir un contrôle plus fin sur la façon dont un membre est accédé sur chaque objet.

const longueurMaxDuNom = 10;

class Salarie {
    private _nomComplet: string;

    get nomComplet(): string {
        return this._nomComplet;
    }

    set nomComplet(nouveauNom: string) {
        if (nouveauNom && nouveauNom.length > longueurMaxDuNom) {
            throw new Error("Erreur Longueur maxi du nom atteinte, longueur max autorisee = " + longueurMaxDuNom);
        }
        
        this._nomComplet = nouveauNom;
    }
}

let salarie = new Salarie();
salarie.nomComplet = "Toto Hello";
if (employee.nomComplet) {
    console.log(employee.nomComplet);
}

Références à lire :

Typescript getter setter : liens internes

https://128mots.com/index.php/category/graphes/

https://128mots.com/index.php/category/python/

Typescript getter setter Plus d’informations:

Le stockage des classes peut se faire dans des fichiers séparés, dans ce cas il s’agit d’une déclaration de module.

Les modules permettent de rendre accessible la classe en dehors du fichier. La classes doit dans un premier temps être exportée via « export » pour être visible exemple de personne.ts:

Utilisation des classes

Comme dans les autres langages une classe permet de créer des objets et regroupe des variables et des fonctions qui sont fortement liées « Highly Related »

TypeScript est un langage à typage fort typé, orienté objet et compilé. TypeScript est un sur-ensemble typé de JavaScript compilé en JavaScript. TypeScript est JavaScript et quelques fonctionnalités supplémentaires.

La documentation de typescript est disponible sur ce lien : https://www.typescriptlang.org/docs/home.html

Angular est un framework pour construire des applications clientes, il se base sur HTML/CSS et JavaScript/TypeScript.

Angular propose les avantages suivants :

  1. Revealing Module Pattern : permet d’organiser le code en un ou plusieurs modules et donne une meilleure structure.
  2. Architecture propre et structurée.
  3. Code réutilisable.
  4. Application plus facilement testable.

ANGULAR en moins de 128 mots – Composants Angular – Partie 6

Construction d’application par bloc

Les composants sont comme des blocs de construction dans une application Angular.

Les composants sont définis à l’aide du décorateur @component. Un composant possède un sélecteur, un modèle, un style et d’autres propriétés, à l’aide desquels il spécifie les métadonnées requises pour traiter le composant.

Exemple d’architecture en bloc de composant Angular

AppComponent est le composant racine de notre application. C’est la base de l’arborescence des composants de l’application Angular.

https://angular.io/guide/architecture-modules

Pour générer un composant la commande est :

ng g component MyComponent

Exemple de composant :

import { Component } from "@angular/core";

@Component({
  selector: "articles",
  template: "<h2>Article</h2>"
})
export class ArticlesComponent {
}

A noter que si vous n’avez pas utilisé la commande de génération de composant, il faut alors manuellement ajouter le composant dans le fichier src/app/app.module.ts dans les imports

import { BrowserModule } from "@angular/platform-browser";
import { NgModule } from "@angular/core";
import { AppComponent } from "./app.component";
import { ArticlesComponent } from "./articles.component";

@NgModule({
  declarations: [AppComponent, ArticlesComponent],
  imports: [BrowserModule, ArticlesComponent],
  providers: [],
  bootstrap: [AppComponent]
})
export class AppModule {}

ANGULAR en moins de 128 mots – TypeScript – Partie 4

Cet article fait suite aux trois premiers sur le sujet ANGULAR et porte sur le langage TypeScript :

Concept de “type assertion”

L’assertion de type est un moyen de dire au compilateur TypeScript quel est le type d’une variable. L’assertion de type est similaire à la conversion de type dans d’autres langages, mais dans TypeScript, ce n’est qu’une fonction de compilation.

let testComplet: any = "Test Assertion de type";
let test = (<string>testComplet).substring(0,4);
console.log(s);

Autre notation :

et testComplet: any = "Test Assertion de type";
let test = (testComplet as string).substring(0,4);
console.log(s);

Arrow Function :

L’utilisation de function arrow supprime la nécessité d’utiliser le mot-clé «function». Les paramètres sont passés entre crochets <> et l’expression de fonction est placée entre crochets {}.

let addition = (a: number, b: number): number => {
            return a + b;
}
addition(1, 2);

In line annotation :

En TypeScript, les annotations de type en ligne permettent de déclarer un objet pour chacune des propriétés de l’objet.

Autre utilisation :

let addition = (paireDeNombre = {nombreA: number,nombreB : number}): number => {
            return a + b;
}

Interface :

Les interfaces permettent de nommer ces types et sont un moyen puissant de définir des contrats dans votre code ainsi que des contrats avec du code en dehors de votre projet.

interface Point{
  x: number,
  y: number
}

Lien vers la documentation de TypeScript : https://www.typescriptlang.org/docs/home.html

ANGULAR en plus de 128 mots – Partie 1

Angular est un framework pour construire des applications clientes, il se base sur HTML/CSS et JavaScript/TypeScript.

Angular propose les avantages suivants :

  • Revealing Module Pattern : permet d’organiser le code en un ou plusieurs modules et donne une meilleure structure.
  • Architecture propre et structurée.
  • Code réutilisable.
  • Application plus facilement testable.

Architecture :

  • Front-End : S’occupe de la logique de présentation. Constitué de HTML / CSS / TypeScript / Angular
  • Backend : S’occupe de la logique métier. Constitué de Data + API

Créer une première application Angular :

NodeJS : L’environnement d’exécution Node.js comprend tout ce dont vous avez besoin pour exécuter un programme écrit en JavaScript. Pour l’installer le lien https://node.js.org

Node Package Manager : il s’agit d’un utilitaire en ligne de commande qui facilite l’installation de packages, la gestion des versions et la gestion des dépendances.

Angular-Cli : une interface de ligne de commande pour automatiser votre flux de travail de développement. Il vous permet de:

  • Créer une nouvelle application Angular.
  • Exécutez un serveur de développement avec prise en charge de “Live Reload” pour prévisualiser votre application pendant le développement.
  • Ajouter des fonctionnalités à votre application Angular.
  • Exécuter des tests unitaires
  • Exécuter les tests de end to end
  • Construire l’application pour le déploiement en production
  • Déployer votre application sur un serveur

Installation de Angular-cli en ligne de commande :

npm install -g @angular-cli

Cette notation avec @ permet aux packages NPM d’être espacés de noms. Chaque utilisateur et organisation sur NPM a sa propre portée et ils sont les seuls à pouvoir y ajouter des packages.

Ceci est utile pour plusieurs raisons:

  • Permet aux organisations d’indiquer clairement quels packages sont «officiels» et lesquels ne le sont pas. Exemple, la portée @angular, assure qu’il a été publié par l’équipe de base Angular.
  • Le nom du package doit être unique à dans sa portée de publication mais pas à l’ensemble du registre npm.
    Exemple, le nom du package http est déjà pris dans le référentiel principal npm, mais Angular peut également avoir @ angular / http.

Pour plus de détails la documentation est consultable à ce lien : https://docs.npmjs.com/

Créer un paquet Angular :

ng new paquet-test-angular

Éditer le code du projet Angular créé :

Je vous conseille d’éditer le code avec l’éditeur VsCode : https://code.visualstudio.com/ ou avec l’éditeur de code Sublime Text https://www.sublimetext.com/

Si vous utilisez vscode la commande suivante peut être utilisée à la racine de votre projet.

code .

Déployer votre projet angular sur le serveur de la machine locale :

ng serve

L’application est alors consultable sur le localhost:4200.

Implémentation Python de l’algorithme de Dijkstra

Cet article fait suite à l’article suivant sur l’algorithme de Dijkstra : https://128mots.com/index.php/2020/02/17/lalgorithme-de-dijkstra-dans-un-graphe-pondere-et-oriente-en-plus-de-128-mots/

Voici l’implémentation Python de l’algorithme

from collections import deque

def dijkstra(graph, vertex):
    queue = deque([vertex])
    distance = {vertex: 0}
    while queue:
        t = queue.popleft()
        print("On visite le sommet " + str(t))
        for voisin in graph[t]:
                queue.append(voisin)
                nouvelle_distance = distance[t] + graph[t][voisin]
                if(voisin not in distance or nouvelle_distance < distance[voisin]):
                    distance[voisin] = nouvelle_distance
                    print("Met à jour le sommet " + str(voisin) + " avec la distance : " + str(nouvelle_distance))
                    
    return distance



#Liste d'ajacence du graphe
graph = {'A':{'B':15,'C':4},'B':{'E':5},'C':{'E':11,'D':2},'D':{'E':3},'E':{}}
distance = dijkstra(graph,'A')
print("Distances" + str(distance))

Implémentation Python du parcours en largeur dans les graphes (BFS)

Cet article fait suite à celui qui porte sur l’algorithme BFS ici : https://128mots.com/index.php/2020/02/11/parcours-en-largeur-dans-les-graphes-bfs/

L’implémentation Python de cet algorithme est la suivante :

from collections import deque

def bfs(graph, vertex):
    queue = deque([vertex])
    distance = {vertex: 0}
    pere = {vertex: None}
    while queue:
    	t = queue.popleft()
    	for voisin in graph[t]:
    		if voisin not in distance:
    			queue.append(voisin)
    			distance[voisin] = distance[t] + 1
    			pere[voisin] = t
    return distance, pere


#Liste d'ajacence du graphe
graph = {
	'A': ['B','C'],
	'B': ['A','C', 'D'],
	'C': ['D'],
	'D': ['C','A']
}

distance,pere = bfs(graph,'A')
print("Distances" + str(distance))
print("Pere = " + str(pere))