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 liczbę wierzchołków function getVerticesCount(graph) { // w macierzy sąsiedztwa jej długość to liczba wierzchołków return graph.length; } // funkcja szukająca najkrótsze ścieżki algorytmem Bellmana-Forda function getShortestPath(graph, start, getWeight) { // dla ułatwienia pobieramy zawczasu liczbę wierzchołków oraz krawędzie const vertices = getVerticesCount(graph); const edges = getAllEdges(graph); // etap 1 - inicjalizacja // tworzymy tablicę poprzedników i wypełniamy ją wartościami null const previous = Array(vertices).fill(null); // tworzymy tablicę odległości i wypełniamy ją nieskończonością const distance = Array(vertices).fill(Number.POSITIVE_INFINITY); // ustawiamy dystans do wierzchołka startowego na 0 distance[start] = 0; // etap 2 - powtarzanie relaksacji // iterujemy V-1 razy for (let i = 0; i < vertices - 1; i++) { // iterujemy po wszystkich krawędziach for (const [u, v] of edges) { const newDistance = distance[u] + getWeight(u, v) // sprawdzamy, czy aktualna ścieżka jest krótsza od znanej if (distance[v] > newDistance) { // ustawiamy nową ścieżkę distance[v] = newDistance; previous[v] = u; } } } // etap 3 - znalezienie cykli // iterujemy po wszystkich krawędziach for (const [u, v] of edges) { // jeśli warunek znany z relaksacji jest prawdziwy, mamy cykl if (distance[v] > distance[u] + getWeight(u, v)) { throw new Error('Znaleziono cykl z wagami ujemnymi'); } } return { distance, previous }; } // funkcja wypisująca najkrótszą ścieżkę między dwoma wierzchołkami // dodatkowy argument to akumulator wyniku function constructShortestPath(previous, startNode, endNode, result = []) { if (startNode === endNode) { // dodajemy wierzchołek do wyniku jeśli początek i wynik są takie same result.push(startNode); } else if (previous[endNode] === null) { // ścieżka nie istnieje result.push('brak ścieżki'); } else { // wywołujemy rekurencyjnie funkcję dla poprzednika constructShortestPath(previous, startNode, previous[endNode], result); // dodajemy węzeł końcowy do wyniku result.push(endNode); // zwracamy wynik 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, 0, generateWeightFunction(graph)); // generujemy ścieżki do wszystkich wierzchołków od wierzchołka 0 // oraz wypisujemy ich długość for (let i = 1; i < graph.length; i++) { console.log(constructShortestPath(result.previous, 0, i), result.distance[i]); }