code. compile. run. debug. share.
// wykorzystamy gotową implementację kopca Fibonacciego stąd: https://www.npmjs.com/package/@tyriar/fibonacci-heap
const { FibonacciHeap } = require('./fibonacciHeap');
// funkcja zwracająca sąsiadów wierzchołka
function getNeighbors(graph, node) {
const result = [];
// iterujemy po wierszu reprezentującym skąd dojdziemy ze wskazanego wierzchołka
for (let i = 0; i < graph.length; i++) {
const edge = graph[node][i];
if (edge !== null) {
result.push(i);
}
}
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 Bellmana-Forda
function getShortestPath(graph, start, getWeight) {
// pobieramy tablicę wierzchołków
const vertices = getAllNodes(graph);
// tworzymy tablicę poprzedników i wypełniamy ją wartościami null
const previous = Array(vertices.length).fill(null);
// tworzymy tablicę odległości i wypełniamy ją nieskończonością
const distance = Array(vertices.length).fill(Number.POSITIVE_INFINITY);
// ustawiamy dystans do wierzchołka startowego na 0
distance[start] = 0;
// tworzymy kolejkę priorytetową
const queue = new FibonacciHeap();
// dodajemy wierzchołki do kolejki; ze względu na implementację kolejki
// musimy przechować referencje do wierzchołków w niej;
// jeżeli napiszesz kolejkę samodzielnie, można tego uniknąć
const queueNodes = Array(vertices.length);
for (let i = 0; i < vertices.length; i++) {
queueNodes[i] = queue.insert(distance[i], i);
}
// dopóki kolejka nie jest pusta...
while (!queue.isEmpty()) {
// ściągamy wierzchołek o najmniejszym priorytecie
const u = queue.extractMinimum().value;
// dla każdego wierzchołka sąsiadującego...
for (const v of getNeighbors(graph, u)) {
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;
// aktualizujemy priorytet w kolejce
queue.decreaseKey(queueNodes[v], newDistance);
}
}
}
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, 0, 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, 1, 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]);
}
"use strict";
/**
* @license
* Copyright Daniel Imms <http://www.growingwiththeweb.com>
* Released under MIT license. See LICENSE in the project root for details.
*/
Object.defineProperty(exports, "__esModule", { value: true });
var node_1 = require("./node");
var nodeListIterator_1 = require("./nodeListIterator");
var FibonacciHeap = /** @class */ (function () {
function FibonacciHeap(compare) {
this._minNode = null;
this._nodeCount = 0;
this._compare = compare ? compare : this._defaultCompare;
}
/**
* Clears the heap's data, making it an empty heap.
*/
FibonacciHeap.prototype.clear = function () {
this._minNode = null;
this._nodeCount = 0;
};
/**
* Decreases a key of a node.
* @param node The node to decrease the key of.
* @param newKey The new key to assign to the node.
*/
FibonacciHeap.prototype.decreaseKey = function (node, newKey) {
if (!node) {
throw new Error('Cannot decrease key of non-existent node');
}
if (this._compare({ key: newKey }, { key: node.key }) > 0) {
throw new Error('New key is larger than old key');
}
node.key = newKey;
var parent = node.parent;
if (parent && this._compare(node, parent) < 0) {
this._cut(node, parent, this._minNode);
this._cascadingCut(parent, this._minNode);
}
if (this._compare(node, this._minNode) < 0) {
this._minNode = node;
}
};
/**
* Deletes a node.
* @param node The node to delete.
*/
FibonacciHeap.prototype.delete = function (node) {
// This is a special implementation of decreaseKey that sets the argument to
// the minimum value. This is necessary to make generic keys work, since there
// is no MIN_VALUE constant for generic types.
var parent = node.parent;
if (parent) {
this._cut(node, parent, this._minNode);
this._cascadingCut(parent, this._minNode);
}
this._minNode = node;
this.extractMinimum();
};
/**
* Extracts and returns the minimum node from the heap.
* @return The heap's minimum node or null if the heap is empty.
*/
FibonacciHeap.prototype.extractMinimum = function () {
var extractedMin = this._minNode;
if (extractedMin) {
// Set parent to null for the minimum's children
if (extractedMin.child) {
var child = extractedMin.child;
do {
child.parent = null;
child = child.next;
} while (child !== extractedMin.child);
}
var nextInRootList = null;
if (extractedMin.next !== extractedMin) {
nextInRootList = extractedMin.next;
}
// Remove min from root list
this._removeNodeFromList(extractedMin);
this._nodeCount--;
// Merge the children of the minimum node with the root list
this._minNode = this._mergeLists(nextInRootList, extractedMin.child);
if (this._minNode) {
this._minNode = this._consolidate(this._minNode);
}
}
return extractedMin;
};
/**
* Returns the minimum node from the heap.
* @return The heap's minimum node or null if the heap is empty.
*/
FibonacciHeap.prototype.findMinimum = function () {
return this._minNode;
};
/**
* Inserts a new key-value pair into the heap.
* @param key The key to insert.
* @param value The value to insert.
* @return node The inserted node.
*/
FibonacciHeap.prototype.insert = function (key, value) {
var node = new node_1.Node(key, value);
this._minNode = this._mergeLists(this._minNode, node);
this._nodeCount++;
return node;
};
/**
* @return Whether the heap is empty.
*/
FibonacciHeap.prototype.isEmpty = function () {
return this._minNode === null;
};
/**
* @return The size of the heap.
*/
FibonacciHeap.prototype.size = function () {
if (this._minNode === null) {
return 0;
}
return this._getNodeListSize(this._minNode);
};
/**
* Joins another heap to this heap.
* @param other The other heap.
*/
FibonacciHeap.prototype.union = function (other) {
this._minNode = this._mergeLists(this._minNode, other._minNode);
this._nodeCount += other._nodeCount;
};
/**
* Compares two nodes with each other.
* @param a The first key to compare.
* @param b The second key to compare.
* @return -1, 0 or 1 if a < b, a == b or a > b respectively.
*/
FibonacciHeap.prototype._defaultCompare = function (a, b) {
if (a.key > b.key) {
return 1;
}
if (a.key < b.key) {
return -1;
}
return 0;
};
/**
* Cut the link between a node and its parent, moving the node to the root list.
* @param node The node being cut.
* @param parent The parent of the node being cut.
* @param minNode The minimum node in the root list.
* @return The heap's new minimum node.
*/
FibonacciHeap.prototype._cut = function (node, parent, minNode) {
node.parent = null;
parent.degree--;
if (node.next === node) {
parent.child = null;
}
else {
parent.child = node.next;
}
this._removeNodeFromList(node);
var newMinNode = this._mergeLists(minNode, node);
node.isMarked = false;
return newMinNode;
};
/**
* Perform a cascading cut on a node; mark the node if it is not marked,
* otherwise cut the node and perform a cascading cut on its parent.
* @param node The node being considered to be cut.
* @param minNode The minimum node in the root list.
* @return The heap's new minimum node.
*/
FibonacciHeap.prototype._cascadingCut = function (node, minNode) {
var parent = node.parent;
if (parent) {
if (node.isMarked) {
minNode = this._cut(node, parent, minNode);
minNode = this._cascadingCut(parent, minNode);
}
else {
node.isMarked = true;
}
}
return minNode;
};
/**
* Merge all trees of the same order together until there are no two trees of
* the same order.
* @param minNode The current minimum node.
* @return The new minimum node.
*/
FibonacciHeap.prototype._consolidate = function (minNode) {
var aux = [];
var it = new nodeListIterator_1.NodeListIterator(minNode);
while (it.hasNext()) {
var current = it.next();
// If there exists another node with the same degree, merge them
var auxCurrent = aux[current.degree];
while (auxCurrent) {
if (this._compare(current, auxCurrent) > 0) {
var temp = current;
current = auxCurrent;
auxCurrent = temp;
}
this._linkHeaps(auxCurrent, current);
aux[current.degree] = null;
current.degree++;
auxCurrent = aux[current.degree];
}
aux[current.degree] = current;
}
var newMinNode = null;
for (var i = 0; i < aux.length; i++) {
var node = aux[i];
if (node) {
// Remove siblings before merging
node.next = node;
node.prev = node;
newMinNode = this._mergeLists(newMinNode, node);
}
}
return newMinNode;
};
/**
* Removes a node from a node list.
* @param node The node to remove.
*/
FibonacciHeap.prototype._removeNodeFromList = function (node) {
var prev = node.prev;
var next = node.next;
prev.next = next;
next.prev = prev;
node.next = node;
node.prev = node;
};
/**
* Links two heaps of the same order together.
*
* @private
* @param max The heap with the larger root.
* @param min The heap with the smaller root.
*/
FibonacciHeap.prototype._linkHeaps = function (max, min) {
this._removeNodeFromList(max);
min.child = this._mergeLists(max, min.child);
max.parent = min;
max.isMarked = false;
};
/**
* Merge two lists of nodes together.
*
* @private
* @param a The first list to merge.
* @param b The second list to merge.
* @return The new minimum node from the two lists.
*/
FibonacciHeap.prototype._mergeLists = function (a, b) {
if (!a) {
if (!b) {
return null;
}
return b;
}
if (!b) {
return a;
}
var temp = a.next;
a.next = b.next;
a.next.prev = a;
b.next = temp;
b.next.prev = b;
return this._compare(a, b) < 0 ? a : b;
};
/**
* Gets the size of a node list.
* @param node A node within the node list.
* @return The size of the node list.
*/
FibonacciHeap.prototype._getNodeListSize = function (node) {
var count = 0;
var current = node;
do {
count++;
if (current.child) {
count += this._getNodeListSize(current.child);
}
current = current.next;
} while (current !== node);
return count;
};
return FibonacciHeap;
}());
exports.FibonacciHeap = FibonacciHeap;
//# sourceMappingURL=fibonacciHeap.js.map
"use strict";
/**
* @license
* Copyright Daniel Imms <http://www.growingwiththeweb.com>
* Released under MIT license. See LICENSE in the project root for details.
*/
Object.defineProperty(exports, "__esModule", { value: true });
var Node = /** @class */ (function () {
function Node(key, value) {
this.parent = null;
this.child = null;
this.degree = 0;
this.isMarked = false;
this.key = key;
this.value = value;
this.prev = this;
this.next = this;
}
return Node;
}());
exports.Node = Node;
//# sourceMappingURL=node.js.map
"use strict";
/**
* @license
* Copyright Daniel Imms <http://www.growingwiththeweb.com>
* Released under MIT license. See LICENSE in the project root for details.
*/
Object.defineProperty(exports, "__esModule", { value: true });
var NodeListIterator = /** @class */ (function () {
/**
* Creates an Iterator used to simplify the consolidate() method. It works by
* making a shallow copy of the nodes in the root list and iterating over the
* shallow copy instead of the source as the source will be modified.
* @param start A node from the root list.
*/
function NodeListIterator(start) {
this._index = -1;
this._items = [];
var current = start;
do {
this._items.push(current);
current = current.next;
} while (start !== current);
}
/**
* @return Whether there is a next node in the iterator.
*/
NodeListIterator.prototype.hasNext = function () {
return this._index < this._items.length - 1;
};
/**
* @return The next node.
*/
NodeListIterator.prototype.next = function () {
return this._items[++this._index];
};
return NodeListIterator;
}());
exports.NodeListIterator = NodeListIterator;
//# sourceMappingURL=nodeListIterator.js.map
Compiling Program...
Standard Input:
Interactive Console
Text
Program is not being debugged. Click "Debug" button to start program in debug mode.
| # | Function | File:Line |
|---|
| Variable | Value |
|---|
| Register | Value |
|---|
| Expression | Value |
|---|
| # | Description |
|---|