les Algorithmes de Parcours de Graphes : Plus Court Chemin

// Fonction pour trouver le plus court chemin à partir d'un sommet source
function dijkstra(graph, start) {
    const distances = {};
    const visited = new Set();
    const minHeap = new MinHeap();

    // Initialisation des distances
    for (let vertex in graph) {
        distances[vertex] = Infinity;
    }
    distances[start] = 0;

    minHeap.insert(start, 0);

    // Tant que le tas n'est pas vide
    while (minHeap.heap.length > 0) {
        const { key: current, value: currentDistance } = minHeap.extractMin();

        if (visited.has(current)) continue;
        visited.add(current);

        for (let neighbor in graph[current]) {
            const newDistance = currentDistance + graph[current][neighbor];

            if (newDistance < distances[neighbor]) {
                distances[neighbor] = newDistance;
                minHeap.insert(neighbor, newDistance);
            }
        }
    }

    return distances;
}

// Exemple d'utilisation
const graph = {
    A: { B: 1, C: 4 },
    B: { A: 1, C: 2, D: 5 },
    C: { A: 4, B: 2, D: 1 },
    D: { B: 5, C: 1 }
};

const distances = dijkstra(graph, 'A');
console.log(distances); // Output: { A: 0, B: 1, C: 3, D: 4 }

// Fonction pour trouver le plus court chemin dans un graphe avec des poids négatifs
function bellmanFord(graph, start) {
    const distances = {};
    const edges = [];

    // Initialisation des distances
    for (let vertex in graph) {
        distances[vertex] = Infinity;
        for (let neighbor in graph[vertex]) {
            edges.push([vertex, neighbor, graph[vertex][neighbor]]);
        }
    }
    distances[start] = 0;

    // Relâchement des arêtes |V|-1 fois
    for (let i = 0; i < Object.keys(graph).length - 1; i++) {
        for (let [u, v, weight] of edges) {
            if (distances[u] + weight < distances[v]) {
                distances[v] = distances[u] + weight;
            }
        }
    }

    // Détection de cycle de poids négatif
    for (let [u, v, weight] of edges) {
        if (distances[u] + weight < distances[v]) {
            console.log("Graph contains a negative-weight cycle");
            return null;
        }
    }

    return distances;
}

// Exemple d'utilisation
const graph = {
    A: { B: -1, C: 4 },
    B: { C: 3, D: 2, E: 2 },
    C: {},
    D: { B: 1, C: 5 },
    E: { D: -3 }
};

const distances = bellmanFord(graph, 'A');
console.log(distances); // Output: { A: 0, B: -1, C: 2, D: -2, E: 1 }

// Fonction pour trouver le plus court chemin entre toutes les paires de sommets
function floydWarshall(graph) {
    const dist = {};
    const vertices = Object.keys(graph);

    // Initialisation de la matrice de distance
    vertices.forEach(v => {
        dist[v] = {};
        vertices.forEach(u => {
            if (v === u) {
                dist[v][u] = 0;
            } else if (graph[v][u] != null) {
                dist[v][u] = graph[v][u];
            } else {
                dist[v][u] = Infinity;
            }
        });
    });

    // Mise à jour de la matrice de distance
    vertices.forEach(k => {
        vertices.forEach(i => {
            vertices.forEach(j => {
                if (dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            });
        });
    });

    return dist;
}

// Exemple d'utilisation
const graph = {
    A: { A: 0, B: 3, C: Infinity, D: 7 },
    B: { A: 8, B: 0, C: 2, D: Infinity },
    C: { A: 5, B: Infinity, C: 0, D: 1 },
    D: { A: 2, B: Infinity, C: Infinity, D: 0 }
};

const distances = floydWarshall(graph);
console.log(distances);
/*
Output:
{
  A: { A: 0, B: 3, C: 5, D: 6 },
  B: { A: 8, B: 0, C: 2, D: 3 },
  C: { A: 5, B: 8, C: 0, D: 1 },
  D: { A: 2, B: 5, C: 7, D: 0 }
}
*/