online compiler and debugger for c/c++

// funkcja zwracająca wszystkie krawędzie grafu function getAllEdges(graph) { // zmienna przechowująca wynik const result = []; // iterujemy po wszystkich elementach macierzy sąsiedztwa for (let i = 0; i < graph.length; i++) { for (let j = 0; j < graph[i].length; j++) { // jeśli istnieje krawędź, zapiszmy ją do wyniku if (graph[i][j] !== null) { result.push([i, j]); } } } // zwracamy pary krawędzi return result; } // funkcja zwracająca listę wszystkich wierzchołków function getAllNodes(graph) { // wierzchołki to liczby od 0 do N, gdzie N to rozmiar macierzy return [...Array(graph.length).keys()]; } // funkcja szukająca najkrótsze ścieżki algorytmem Floyda-Warshalla function getShortestPath(graph, getWeight) { // pobieramy wszystkie wierzchołki const vertices = getAllNodes(graph); // inicjalizujemy macierz odległości const distance = Array(vertices.length).fill().map(() => Array(vertices.length).fill(Number.POSITIVE_INFINITY)); // inicjalizujemy macierz następników const next = Array(vertices.length).fill().map(() => Array(vertices.length).fill(null)); // ustawiamy wartości w macierzach dla krawędzi for (const [u, v] of getAllEdges(graph)) { distance[u][v] = getWeight(u, v); next[u][v] = v; } // ustawiamy wartości w macierzach dla wierzchołków for (const v of vertices) { distance[v][v] = 0; next[v][v] = v; } // główna, potrójna pętla algorytmu; my będziemy iterować od 0 for (let k = 0; k < vertices.length; k++) { for (let i = 0; i < vertices.length; i++) { for (let j = 0; j < vertices.length; j++) { const newDistance = distance[i][k] + distance[k][j]; // sprawdzamy czy aktualna ścieżka jest mniejsza if (distance[i][j] > newDistance) { // przypisujemy nową odległość distance[i][j] = newDistance; // przypisujemy poprawnego następnika next[i][j] = next[i][k]; } } } } return { distance, next } } // funkcja wypisująca najkrótszą ścieżkę między dwoma wierzchołkami function constructShortestPath(next, startNode, endNode) { // jeśli nie ma drogi, zwracamy pustą tablicę if (next[startNode][endNode] === null) { return []; } // ścieżkę zaczynamy od startego węzła const result = [startNode]; // tak długo jak u jest różny od końcowego węzłą... let u = startNode; while (u !== endNode) { // pobieramy następnik u = next[u][endNode]; // dodajemy go do rezultatu result.push(u); } return result; } // przykładowy graf z wieloma połączeniami const graph = [ [null, 5, null, null, null, 1, null, null, 3], [null, null, -1, 3, null, null, null, null, null], [null, null, null, null, 2, null, null, null, 1], [null, null, null, null, null, 2, null, null, null], [null, null, null, null, null, null, null, 4, null], [1, null, null, -2, null, null, null, null, null], [null, null, null, null, null, 0, null, null, null], [null, null, null, null, null, null, 1, null, null], [null, null, null, null, -2, null, 6, null, null], ]; // funkcja generująca funkcję wagowa function generateWeightFunction(graph) { return (u, v) => graph[u][v]; } // generujemy najkrótsze ścieżki od wierzchołka 0 const result = getShortestPath(graph, generateWeightFunction(graph)); // generujemy ścieżki do wszystkich par wierzchołków // oraz wypisujemy ich długość for (let i = 0; i < graph.length; i++) { console.log(`${i}:`); for (let j = 0; j < graph.length; j++) { if (i === j) { continue; } console.log( constructShortestPath(result.next, i, j).join('->') + ', długość ' + result.distance[i][j] ); } console.log('---') }