Graph Data Structure

gistfile1.ts

interface Edge {
    node: string;
    weight: number;
}

class Graph {
    public adjList: Map<string, Edge[]>

    constructor()
    {
        this.adjList = new Map();
    }

    addEdge(nodeA: string, nodeB: string, weight: number)
    {
        if (!this.adjList.has(nodeA))
        {
            this.adjList.set(nodeA, []);
        }

        if (!this.adjList.has(nodeB))
        {
            this.adjList.set(nodeB, []);
        }

        this.adjList.get(nodeA)?.push({node: nodeB, weight})
        this.adjList.get(nodeB)?.push({node: nodeA, weight})
    }

    dikjstra(start: string, target: string)
    {
        let queue = new PriorityQueue();

        let visited: {[key: string] : boolean} = {};
        let distances: {[key: string]: number} = {};
        let path: {[key: string]: string} = {};

        for (let key of this.adjList.keys()) {
            distances[key] = start === key ? 0 : Infinity;
        }

        visited[start] = true;
        queue.queue({node: start, weight: 0});

        while(!queue.empty())
        {
            let next = queue.dequeue();

            if (!next) {
                continue;
            }

            if (next.node === target) {
                let pathString = target;
                let nextNode = target;
                let visited: {[key: string]: boolean} = {};
    
                while(path[nextNode] && !visited[nextNode])
                {
                    pathString = `${path[nextNode]} ${pathString}`
                    visited[nextNode] = true;
                    nextNode = path[nextNode];
                }
    
                return pathString;
            }

            let edges = this.adjList.get(next?.node) || [];
            visited[next.node] = true;

            edges.forEach((edge) => {
                if (next) {
                    if (distances[next.node] + edge.weight < distances[edge.node]) {
                        distances[edge.node] = distances[next.node] + edge.weight;
                        path[edge.node] = next.node;
                        queue.queue(edge);
                    }
                }
            });
        }

        return null;
    }
}

class PriorityQueue {
    public items: Edge[];

    constructor()
    {
        this.items = [];
    }

    queue(item: Edge)
    {
        if (this.items.length == 0) {
            this.items.push(item)
            return;
        }

        for(let i = 0; i < this.items.length; i++) {
            if (this.items[i].weight > item.weight)
            {
                this.items.splice(i, 0, item);
                return;
            }
        }

        this.items.push(item)
    }

    dequeue()
    {
        return this.items.shift();
    }

    empty()
    {
        return this.items.length === 0;
    }
}

let graph = new Graph();