let graph = {};
let nodes = new vis.DataSet();
let edges = new vis.DataSet();
let network = null;
// Initialisation de la visualisation du graphe
function initGraphVisualization() {
const container = document.getElementById('graph-visualization');
const data = {
nodes: nodes,
edges: edges,
};
const options = {
edges: {
arrows: {
to: { enabled: false } // Désactive les flèches
},
font: { size: 12, color: 'black' },
labelHighlightBold: true,
smooth: {
type: 'straight', // Utilise des traits droits pour les
arêtes
roundness: 0
}
},
nodes: {
font: { size: 16, color: 'black' },
shape: 'circle',
},
};
network = new vis.Network(container, data, options);
}
// Fonction pour ajouter une arête
function addEdge() {
const node1 = document.getElementById('node1').value.toUpperCase();
const node2 = document.getElementById('node2').value.toUpperCase();
const weight = parseInt(document.getElementById('weight').value);
if (!node1 || !node2 || isNaN(weight)) {
alert("Veuillez remplir tous les champs correctement.");
return;
}
// Ajouter les nœuds s'ils n'existent pas
if (!nodes.get(node1)) {
nodes.add({ id: node1, label: node1 });
}
if (!nodes.get(node2)) {
nodes.add({ id: node2, label: node2 });
}
// Ajouter l'arête
edges.add({ from: node1, to: node2, label: weight.toString(), color:
'black' });
// Mettre à jour le graphe en mémoire
if (!graph[node1]) graph[node1] = {};
if (!graph[node2]) graph[node2] = {};
graph[node1][node2] = weight;
graph[node2][node1] = weight;
}
// Fonction pour exécuter Dijkstra
function runDijkstra() {
const startNode = prompt("Entrez le noeud de départ:").toUpperCase();
if (!graph[startNode]) {
alert("Noeud de départ invalide!");
return;
}
const { distances, steps } = dijkstra(startNode);
displaySteps(steps);
highlightPath(distances);
}
// Algorithme de Dijkstra
function dijkstra(startNode) {
let distances = {};
let previous = {};
let nodesQueue = new PriorityQueue();
// Initialisation des distances
for (let node in graph) {
if (node === startNode) {
distances[node] = 0;
nodesQueue.enqueue(node, 0);
} else {
distances[node] = Infinity;
nodesQueue.enqueue(node, Infinity);
}
previous[node] = null;
}
let steps = [];
steps.push({ ...distances });
while (!nodesQueue.isEmpty()) {
let smallest = nodesQueue.dequeue().element;
// Mettre à jour les distances des voisins
for (let neighbor in graph[smallest]) {
let alt = distances[smallest] + graph[smallest][neighbor];
if (alt < distances[neighbor]) {
distances[neighbor] = alt;
previous[neighbor] = smallest;
nodesQueue.enqueue(neighbor, alt);
}
}
// Enregistrer l'étape actuelle
steps.push({ ...distances });
}
return { distances, steps };
}
// Fonction pour afficher les étapes dans le tableau
function displaySteps(steps) {
const tableHeader = document.getElementById('table-header');
const tableBody = document.getElementById('table-body');
tableHeader.innerHTML = '';
tableBody.innerHTML = '';
// Créer l'en-tête du tableau
const nodesList = Object.keys(graph);
for (let node of nodesList) {
let th = document.createElement('th');
th.textContent = node;
tableHeader.appendChild(th);
}
// Remplir le tableau avec les étapes
for (let step of steps) {
let row = document.createElement('tr');
for (let node of nodesList) {
let cell = document.createElement('td');
cell.textContent = step[node] !== Infinity ? step[node] : '∞';
row.appendChild(cell);
}
tableBody.appendChild(row);
}
}
// Fonction pour mettre en évidence le chemin minimal
function highlightPath(distances) {
const minNode = Object.keys(distances).reduce((a, b) => distances[a] <
distances[b] ? a : b);
edges.update(edges.get().map(edge => {
if (edge.from === minNode || edge.to === minNode) {
edge.color = 'blue';
} else {
edge.color = 'black';
}
return edge;
}));
}
// Classe PriorityQueue pour gérer la file de priorité
class PriorityQueue {
constructor() {
this.values = [];
}
enqueue(element, priority) {
this.values.push({ element, priority });
this.sort();
}
dequeue() {
return this.values.shift();
}
sort() {
this.values.sort((a, b) => a.priority - b.priority);
}
isEmpty() {
return this.values.length === 0;
}
}
// Initialisation
initGraphVisualization();
