Это моя реализация графа, чтобы получить кратчайший путь между А и В.
class Queue {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
offer(item) {
const p = new QueueNode(item);
this.size++;
if (this.head === null) {
this.head = p;
this.tail = p;
return;
}
this.tail.next = p;
this.tail = p;
}
poll() {
if (this.size === 0) {
throw TypeError("Can't deque off an empty queue.");
}
this.size--;
const item = this.head;
this.head = this.head.next;
return item.val;
}
peek() {
if (this.size === 0) {
throw TypeError("Empty Queue.")
}
return this.head.val;
}
isEmpty() {
return this.head === null;
}
}
class QueueNode {
constructor(item) {
this.val = item;
this.next = null;
}
}
class Graph {
constructor(directed = false) {
this.numVertices = 0;
this.directed = directed;
this.dict = {}
}
addEdge(v1, v2, weight = 1) {
let p, q;
if (v1 in this.dict) {
p = this.dict[v1];
} else {
p = new GraphNode(v1);
this.dict[v1] = p;
this.numVertices++;
}
if (v2 in this.dict) {
q = this.dict[v2];
} else {
q = new GraphNode(v2);
this.dict[v2] = q;
this.numVertices++;
}
p.addEdge(q);
if (!this.directed) {
q.addEdge(p);
}
}
stringify() {
for (const [key, value] of Object.entries(this.dict)) {
console.log(`${key}: ${[...value.adjacencySet].map(x => x.data)}`);
}
}
buildDistanceTable(source) {
let p;
if (this.dict[source] === undefined) {
throw TypeError('Vertex not present in graph')
} else {
p = this.dict[source];
}
const distanceTable = {};
for (const [key, value] of Object.entries(this.dict)) {
distanceTable[key] = [-1, -1];
}
distanceTable[p.data] = [0, p.data];
const queue = new Queue();
queue.offer(p);
while (!queue.isEmpty()) {
let curr = queue.poll();
let curr_distance = distanceTable[curr.data][0];
curr.adjacencySet.forEach((item) => {
if (distanceTable[item.data] === -1) {
distanceTable[item.data] = [1 + curr_distance, curr.data];
console.log(distanceTable);
if (item.adjacencySet.length > 0) {
queue.offer(item);
}
}
})
}
return distanceTable;
}
shortestPath(source, destination) {
const distanceTable = this.buildDistanceTable(source);
const path = [destination];
let prev = distanceTable[destination][1];
while (prev !== -1 && prev !== source) {
path.unshift(prev);
prev = distanceTable[prev][1];
}
if (prev === null) {
console.log("There's no path from source to destination");
} else {
path.unshift(source);
path.map(item => {
console.log(item);
});
}
}
}
class GraphNode {
constructor(data) {
this.data = data;
this.adjacencySet = new Set();
}
addEdge(node) {
this.adjacencySet.add(node)
}
}
graph = new Graph(directed = false);
graph.addEdge(0, 1);
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 3);
graph.addEdge(1, 4);
graph.addEdge(3, 5);
graph.addEdge(5, 4);
graph.addEdge(3, 6);
graph.addEdge(6, 7);
graph.addEdge(0, 7);
graph.stringify();
graph.shortestPath(1, 7);
Когда я запускаю это, это дает 1, 7, однако это не самый короткий путь.Что я тут не так делаю.