dijkstra's algorithm

dijkstra-priority-queue.py

import math
import collections
from heapq import *

class Node:
    def __init__(self, id):
        self.id = id
        self.edges = []

    def add_route(self, to, cost):
        self.edges.append({
            "to": to,
            "cost": cost
        })

    def __lt__(self, t):
        return True


def dijkstra(nodes):
    start = nodes[0]
    end = nodes[-1]

    distance_from_start = {n: math.inf for n in nodes}
    distance_from_start[start] = 0

    minHeap = []
    heappush(minHeap, (0, start))

    while minHeap:
        (distance, current) = heappop(minHeap)

        if distance_from_start[current] < distance:
            continue

        for edge in current.edges:
            cost = edge["cost"]
            to = edge["to"]

            if cost + distance_from_start[current] < distance_from_start[to]:
                distance_from_start[to] = cost + distance_from_start[current]
                heappush(minHeap, (cost + distance_from_start[current], to))
    
    return distance_from_start[end]

def add_node(f, to, weight):
    f.add_route(to, weight)

def main():
    node1 = Node(1)
    node2 = Node(2)
    node3 = Node(3)
    node4 = Node(4)
    node5 = Node(5)
    node6 = Node(6)
    node7 = Node(7)

    add_node(node1, node2, 10)
    add_node(node1, node3, 16)
    add_node(node1, node4, 12)
    add_node(node2, node3, 18)
    add_node(node2, node5, 4)
    add_node(node4, node3, 3)
    add_node(node3, node6, 1)
    add_node(node6, node7, 9)
    add_node(node5, node7, 21)

    dist = dijkstra([node1, node2, node3, node4, node5, node6, node7])

    print(dist)


main()

dijkstra-with-way.js

function dijkstra(nodes) {
    const start = nodes[0]


    const visited = new Set()
    const distanceFromStart = new Map()

    distanceFromStart.set(start, {distance: 0})

    for (const n of nodes) {
        if(n != start) {
            distanceFromStart.set(n, {distance: Number.MAX_VALUE})
        }
    }

    let current = start
    let routes = new Map()

    while(current != null) {
        visited.add(current)

        for(const edge of current.edges) {
            if(edge.cost + distanceFromStart.get(current).distance < distanceFromStart.get(edge.to).distance) {
                distanceFromStart.set(edge.to, {distance: edge.cost + distanceFromStart.get(current).distance})
                routes.set(edge.to, current)
            }
        }

        current = null
        let minNodeDistance = Number.MAX_VALUE
        for(const n of distanceFromStart.keys()) {
            if(!visited.has(n) && distanceFromStart.get(n).distance < minNodeDistance) {
                minNodeDistance = distanceFromStart.get(n).distance

                current = n
            }
        }
    }
    const path = []
    const endNode = nodes[nodes.length - 1]
    let n = nodes[nodes.length - 1]
    while(n != null) {
        path.push(n)
        n = routes.get(n)
    }

    return [distanceFromStart.get(endNode).distance, path.reverse()]
}

function createNode(id) {
    return {
        edges: [],
        id: id,
    };
}
function addNode(from, to, cost) {
    from.edges.push({
        to: to,
        cost: cost
    });
}
function createNodes() {
    const node1 = createNode(1);
    const node2 = createNode(2);
    const node3 = createNode(3);
    const node4 = createNode(4);
    const node5 = createNode(5);
    const node6 = createNode(6);
    const node7 = createNode(7);

    addNode(node1, node2, 10)
    addNode(node1, node3, 16)
    addNode(node1, node4, 12)
    addNode(node2, node3, 18)
    addNode(node2, node5, 4)
    addNode(node4, node3, 3)
    addNode(node3, node6, 1)
    addNode(node6, node7, 9)
    addNode(node5, node7, 21)

    return [node1, node2, node3, node4, node5, node6, node7];
}
const nodes = createNodes();
console.log(dijkstra(nodes))

dijkstra.js

function dijkstra(nodes) {
    const start = nodes[0]


    const visited = new Set()
    const distanceFromStart = new Map()

    distanceFromStart.set(start, {distance: 0})

    for (const n of nodes) {
        if(n != start) {
            distanceFromStart.set(n, {distance: Number.MAX_VALUE})
        }
    }

    let current = start
    while (current != null) {
        visited.add(current)
        for(const edge of current.edges) {
            if(edge.cost + distanceFromStart.get(current).distance < distanceFromStart.get(edge.to).distance) {
                distanceFromStart.set(edge.to, {distance: edge.cost + distanceFromStart.get(current).distance})
            }
        }
        let minNodeDistance = Number.MAX_VALUE
        current = null

        for(const n of distanceFromStart.keys()) {
            if(!visited.has(n) &&  distanceFromStart.get(n).distance < minNodeDistance ) {
                minNodeDistance = distanceFromStart.get(n).distance
                current = n
            }
        }
    }

    return distanceFromStart.get(nodes[nodes.length - 1]).distance
}

function createNode(id) {
    return {
        edges: [],
        id: id,
    };
}
function addNode(from, to, cost) {
    from.edges.push({
        to: to,
        cost: cost
    });
}
function createNodes() {
    const node1 = createNode(1);
    const node2 = createNode(2);
    const node3 = createNode(3);
    const node4 = createNode(4);
    const node5 = createNode(5);
    const node6 = createNode(6);
    const node7 = createNode(7);

    addNode(node1, node2, 10)
    addNode(node1, node3, 16)
    addNode(node1, node4, 12)
    addNode(node2, node3, 18)
    addNode(node2, node5, 4)
    addNode(node4, node3, 3)
    addNode(node3, node6, 1)
    addNode(node6, node7, 9)
    addNode(node5, node7, 21)

    return [node1, node2, node3, node4, node5, node6, node7];
}
const nodes = createNodes();
console.log(dijkstra(nodes))