Skip to content

Commit 59f61dc

Browse files
trekhlebtrekhleb
committed
Add dijkstra.
1 parent 119cddc commit 59f61dc

5 files changed

Lines changed: 136 additions & 2 deletions

File tree

‎README.md‎

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -65,11 +65,11 @@
6565
* **Graph**
6666
* [Depth-First Search](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/depth-first-search) (DFS)
6767
* [Breadth-First Search](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/breadth-first-search) (BFS)
68+
* [Dijkstra Algorithm](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/dijkstra) - finding shortest path
69+
* Bellman Ford
6870
* Detect Cycle
6971
* Topological Sorting
70-
* Dijkstra Algorithm to Find Shortest Path
7172
* Eulerian path, Eulerian circuit
72-
* Bellman Ford
7373
* Strongly Connected Component algorithm
7474
* Shortest Path Faster Algorithm (SPFA)
7575
* **Minimum Spanning Tree**
@@ -84,6 +84,7 @@
8484

8585
* **Greedy**
8686
* [Unbound Knapsack Problem](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/knapsack-problem)
87+
* [Dijkstra Algorithm](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/dijkstra) - finding shortest path
8788
* **Divide and Conquer**
8889
* [Euclidean Algorithm](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/euclidean-algorithm) - calculate the Greatest Common Divisor (GCD)
8990
* [Permutations](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/permutations) (with and without repetitions)

‎src/algorithms/graph/dijkstra/README.md‎

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
# Dijkstra's Algorithm
2+
3+
Dijkstra's algorithm is an algorithm for finding the shortest
4+
paths between nodes in a graph, which may represent, for example,
5+
road networks.
6+
7+
The algorithm exists in many variants; Dijkstra's original variant
8+
found the shortest path between two nodes, but a more common
9+
variant fixes a single node as the "source" node and finds
10+
shortest paths from the source to all other nodes in the graph,
11+
producing a shortest-path tree.
12+
13+
![Dijkstra](https://upload.wikimedia.org/wikipedia/commons/5/57/Dijkstra_Animation.gif)
14+
15+
Dijkstra's algorithm to find the shortest path between `a` and `b`.
16+
It picks the unvisited vertex with the lowest distance,
17+
calculates the distance through it to each unvisited neighbor,
18+
and updates the neighbor's distance if smaller. Mark visited
19+
(set to red) when done with neighbors.
20+
21+
## References
22+
23+
- [Wikipedia](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm)
24+
- [On YouTube by Nathaniel Fan](https://www.youtube.com/watch?v=gdmfOwyQlcI)
25+
- [On YouTube by Tushar Roy](https://www.youtube.com/watch?v=lAXZGERcDf4)

‎src/algorithms/graph/dijkstra/__test__/dijkstra.test.js‎

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
import GraphVertex from '../../../../data-structures/graph/GraphVertex';
2+
import GraphEdge from '../../../../data-structures/graph/GraphEdge';
3+
import Graph from '../../../../data-structures/graph/Graph';
4+
import dijkstra from '../dijkstra';
5+
6+
describe('dijkstra', () => {
7+
it('should find minimum paths to all vertices', () => {
8+
const vertexA = new GraphVertex('A');
9+
const vertexB = new GraphVertex('B');
10+
const vertexC = new GraphVertex('C');
11+
const vertexD = new GraphVertex('D');
12+
const vertexE = new GraphVertex('E');
13+
const vertexF = new GraphVertex('F');
14+
const vertexG = new GraphVertex('G');
15+
const vertexH = new GraphVertex('H');
16+
17+
const edgeAB = new GraphEdge(vertexA, vertexB, 4);
18+
const edgeAE = new GraphEdge(vertexA, vertexE, 7);
19+
const edgeAC = new GraphEdge(vertexA, vertexC, 3);
20+
const edgeBC = new GraphEdge(vertexB, vertexC, 6);
21+
const edgeBD = new GraphEdge(vertexB, vertexD, 5);
22+
const edgeEC = new GraphEdge(vertexE, vertexC, 8);
23+
const edgeED = new GraphEdge(vertexE, vertexD, 2);
24+
const edgeDC = new GraphEdge(vertexD, vertexC, 11);
25+
const edgeDG = new GraphEdge(vertexD, vertexG, 10);
26+
const edgeDF = new GraphEdge(vertexD, vertexF, 2);
27+
const edgeFG = new GraphEdge(vertexF, vertexG, 3);
28+
const edgeEG = new GraphEdge(vertexE, vertexG, 5);
29+
30+
const graph = new Graph();
31+
graph
32+
.addVertex(vertexH)
33+
.addEdge(edgeAB)
34+
.addEdge(edgeAE)
35+
.addEdge(edgeAC)
36+
.addEdge(edgeBC)
37+
.addEdge(edgeBD)
38+
.addEdge(edgeEC)
39+
.addEdge(edgeED)
40+
.addEdge(edgeDC)
41+
.addEdge(edgeDG)
42+
.addEdge(edgeDF)
43+
.addEdge(edgeFG)
44+
.addEdge(edgeEG);
45+
46+
const distances = dijkstra(graph, vertexA);
47+
48+
expect(distances).toEqual({
49+
H: Infinity,
50+
A: 0,
51+
B: 4,
52+
E: 7,
53+
C: 3,
54+
D: 9,
55+
G: 12,
56+
F: 11,
57+
});
58+
});
59+
});

‎src/algorithms/graph/dijkstra/dijkstra.js‎

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
import PriorityQueue from '../../../data-structures/priority-queue/PriorityQueue';
2+
3+
/**
4+
* @param {Graph} graph
5+
* @param {GraphVertex} startVertex
6+
*/
7+
export default function dijkstra(graph, startVertex) {
8+
const distances = {};
9+
const visitedVertices = {};
10+
const queue = new PriorityQueue();
11+
12+
// Init all distances with infinity assuming that currently we can't reach
13+
// any of the vertices except start one.
14+
Object.keys(graph.vertices).forEach((vertexKey) => {
15+
distances[vertexKey] = Infinity;
16+
});
17+
distances[startVertex.getKey()] = 0;
18+
19+
// Init vertices queue.
20+
queue.add(startVertex, distances[startVertex.getKey()]);
21+
22+
while (!queue.isEmpty()) {
23+
const currentVertex = queue.poll();
24+
25+
graph.getNeighbors(currentVertex).forEach((neighbor) => {
26+
// Don't visit already visited vertices.
27+
if (!visitedVertices[neighbor.getKey()]) {
28+
// Update distances to every neighbor from current vertex.
29+
const edge = graph.findEdge(currentVertex, neighbor);
30+
31+
const existingDistanceToNeighbor = distances[neighbor.getKey()];
32+
const distanceToNeighborFromCurrent = distances[currentVertex.getKey()] + edge.weight;
33+
34+
if (distanceToNeighborFromCurrent < existingDistanceToNeighbor) {
35+
distances[neighbor.getKey()] = distanceToNeighborFromCurrent;
36+
}
37+
38+
// Add neighbor to the queue for further visiting.
39+
queue.add(neighbor, distances[neighbor.getKey()]);
40+
}
41+
});
42+
43+
// Add current vertex to visited ones.
44+
visitedVertices[currentVertex.getKey()] = currentVertex;
45+
}
46+
47+
return distances;
48+
}

‎src/data-structures/graph/Graph.js‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -71,6 +71,7 @@ export default class Graph {
7171
/**
7272
* @param {GraphVertex} startVertex
7373
* @param {GraphVertex} endVertex
74+
* @return {(GraphEdge|null)}
7475
*/
7576
findEdge(startVertex, endVertex) {
7677
const vertex = this.getVertexByKey(startVertex.getKey());

0 commit comments

Comments
 (0)