Practice/Dijkstra's_algorithm.js at main · dzevakov/Practice · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
const graph = {
    start: {
        a: 5,
        b: 2
    },
    a: {
        c: 4,
        d: 2
    },
    b: {
        a: 8,
        d: 7
    },
    c: {
        d: 6,
        end: 3
    },
    d: {
        end: 1
    },
    end: {}
    },
    costs = {
        a: 5,
        b: 2,
        c: Infinity,
        d: Infinity,
        end: Infinity
    },
    parents = {
        a: 'start',
        b: 'start',
        c: undefined,
        d: undefined,
        end: undefined
    };
    let processed = [],
        neibors = [];

function findCheapestNode() {
    let cheapestNode,
        node,
        cheapestCost = Infinity;
    for(node in costs) {
        if(costs[node] < cheapestCost && !(processed.includes(node))) {
            cheapestCost = costs[node];
            cheapestNode = node;
        }
    }
    return cheapestNode;
}

function newCosts(cheapestNode) {
    for(let node in neibors) {
        if(costs[cheapestNode] + neibors[node] < costs[node]) {
            costs[node] = costs[cheapestNode] + neibors[node];
            parents[node] = cheapestNode;
        }
    }
}

function writePath(parents, init, aim) {
    let item = aim,
        path = [aim];

    while(item !== init) {
        path.push(parents[item]);
        item = parents[item];
    }
    return path.reverse().join(' -> ');
}

function searchPath (map) {
    let cheapestNode = findCheapestNode();
    while(cheapestNode != undefined) {
        neibors = map[cheapestNode];
        newCosts(cheapestNode);
        processed.push(cheapestNode);
        cheapestNode = findCheapestNode();
    }

    return (`${writePath(parents, 'start', 'end')}, total cost - ${costs.end}`);
}

console.log(searchPath(graph));