 👋🏼

# Graph Traversal: Dijkstra

In the last chapter we iterated over a simple graph using Bellman-Ford to find the shortest paths from a single vertex (our source) to all other vertices in the graph.

The complexity of Bellman-Ford is `O(|V| E)`, which can approximate `O(n^2)` if every vertex has at least one outgoing edge. In other words: it's not terribly efficient.

Dijkstra's algorithm requires only one iteration, however and has a complexity of `O(|V| log V)`, which is much more efficient.

As with Bellman-Ford, we'll use a directed, weighted graph with 6 vertices. In addition, we'll setup a memo table with our source S set to 0 and the rest of the vertices set to infinity.

There is a difference here, however, and it's critical! Dijkstra doesn't work with negative edge weights! I have adjusted this graph so that we don't have any negative weights, as you can see. Specifically the edges between S and E as well as C to B. In addition I've added a few edges to show that the algorithm will scale easily regardless of the number of edges involved.

``````//Dijkstra: Shortest path calculation
//on an edge-weighted, directed graph
class MemoTable{
constructor(vertices){
this.S = {name: "S", cost: 0, visited: false};
this.table = [this.S];
for(var vertex of vertices){
this.table.push({name: vertex, cost: Number.POSITIVE_INFINITY, visited: false});
}
};
getCandidateVertices(){
return this.table.filter(entry => {
return entry.visited === false;
});
};
nextVertex(){
const candidates = this.getCandidateVertices();
if(candidates.length > 0){
return candidates.reduce((prev, curr) => {
return prev.cost < curr.cost ? prev : curr;
});
}else{
return null;
}
};
setCurrentCost(vertex, cost){
this.getEntry(vertex).cost =cost;
};
setAsVisited(vertex){
this.getEntry(vertex).visited = true;
};
getEntry(vertex){
return this.table.find(entry => entry.name == vertex);
};
getCost(vertex){
return this.getEntry(vertex).cost;
};
toString(){
console.log(this.table);
}
};
const vertices = ["A", "B","C", "D", "E"];
const graph = [
{from : "S", to :"A", cost: 4},
{from : "S", to :"E", cost: 2},
{from : "A", to :"D", cost: 3},
{from : "A", to :"C", cost: 6},
{from : "A", to :"B", cost: 5},
{from : "B", to :"A", cost: 3},
{from : "C", to :"B", cost: 1},
{from : "D", to :"C", cost: 3},
{from : "D", to :"A", cost: 1},
{from : "E", to: "D", cost: 1}
]
const memo = new MemoTable(vertices);
const evaluate = vertex => {
const edges = graph.filter(path => {
return path.from === vertex.name;
});
for(edge of edges){
const currentVertexCost = memo.getCost(edge.from);
const toVertexCost = memo.getCost(edge.to);
const tentativeCost = currentVertexCost + edge.cost;
if(tentativeCost < toVertexCost){
memo.setCurrentCost(edge.to, tentativeCost);
}
};
memo.setAsVisited(vertex.name);
const next = memo.nextVertex();
if(next) evaluate(next);
}
//kick it off from the source vertex
evaluate(memo.S);
memo.toString();
``````