Skip to content

Instantly share code, notes, and snippets.

@Dviejopomata Dviejopomata/dijsktra.ts
Last active Sep 22, 2017

Embed
What would you like to do?
dijsktra alghoritm in nodejs
class Graph {
public nodes: string[] = [];
public edges: { [key: string]: string[] } = {};
public distances: { from: string, to: string, distance: number }[] = [];
constructor() { }
public addNode(val: string) {
this.nodes.push(val);
return this;
}
public addNodes(...vals: string[]) {
this.nodes.push(...vals);
return this;
}
public addEdge(from: string, to: string, distance: number) {
this.edges[from] = this.edges[from] || []; this.edges[from].push(to);
this.edges[to] = this.edges[to] || []; this.edges[to].push(from);
this.distances.push({ from, to, distance })
return this;
}
}
function calculateDijkstra(graph: Graph, initial: string) {
let visited: { [key: string]: number } = { [initial]: 0 };
let path: any = {};
let nodes = [...graph.nodes];
let currentWeight = 0;
let weight = 0;
while (!!nodes.length) {
let minNode: string = "";
for (let node of nodes) {
if (node in visited) {
if (!minNode) minNode = node;
else if (visited[node] < visited[minNode]) minNode = node
}
}
if (!minNode) break;
nodes = nodes.filter(i => i !== minNode);
currentWeight = visited[minNode];
for (let edge of graph.edges[minNode]) {
let { distance } = graph.distances.find(i => i.from === minNode && i.to === edge);
weight = currentWeight + distance;
if (!(edge in visited) || weight < visited[edge]) {
visited[edge] = weight;
path[edge] = minNode;
}
}
}
return { visited, path };
}
const graph = new Graph()
.addNodes("A", "B", "C", "D", "E")
.addEdge("A", "B", 10)
.addEdge("B", "A", 29)
.addEdge("C", "B", 35)
.addEdge("B", "C", 40)
.addEdge("D", "C", 80)
.addEdge("C", "D", 70)
.addEdge("E", "C", 30)
.addEdge("C", "E", 50)
const c = calculateDijkstra(graph, "C");
console.log(c);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.