FilesExpand file tree

 master

/

Dijkstra.js

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

76 lines (67 loc) · 1.73 KB

 master

/

Dijkstra.js

Copy path

Top

File metadata and controls

• Code
• Blame

76 lines (67 loc) · 1.73 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

/**

* Author: Samarth Jain

* Dijkstra's Algorithm implementation in JavaScript

* Dijkstra's Algorithm calculates the minimum distance between two nodes.

* It is used to find the shortest path.

* It uses graph data structure.

*/

function createGraph (V, E) {

// V - Number of vertices in graph

// E - Number of edges in graph (u,v,w)

const adjList = [] // Adjacency list

for (let i = 0; i < V; i++) {

adjList.push([])

}

for (let i = 0; i < E.length; i++) {

adjList[E[i][0]].push([E[i][1], E[i][2]])

adjList[E[i][1]].push([E[i][0], E[i][2]])

}

return adjList

}

function djikstra (graph, V, src) {

const vis = Array(V).fill(0)

const dist = []

for (let i = 0; i < V; i++) dist.push([10000, -1])

dist[src][0] = 0

for (let i = 0; i < V - 1; i++) {

let mn = -1

for (let j = 0; j < V; j++) {

if (vis[j] === 0) {

if (mn === -1 || dist[j][0] < dist[mn][0]) mn = j

}

}

vis[mn] = 1

for (let j = 0; j < graph[mn].length; j++) {

const edge = graph[mn][j]

if (vis[edge[0]] === 0 && dist[edge[0]][0] > dist[mn][0] + edge[1]) {

dist[edge[0]][0] = dist[mn][0] + edge[1]

dist[edge[0]][1] = mn

}

}

}

return dist

}

export { createGraph, djikstra }

// const V = 9

// const E = [

// [0, 1, 4],

// [0, 7, 8],

// [1, 7, 11],

// [1, 2, 8],

// [7, 8, 7],

// [6, 7, 1],

// [2, 8, 2],

// [6, 8, 6],

// [5, 6, 2],

// [2, 5, 4],

// [2, 3, 7],

// [3, 5, 14],

// [3, 4, 9],

// [4, 5, 10]

// ]

// const graph = createGraph(V, E)

// const distances = djikstra(graph, V, 0)

/**

* The first value in the array determines the minimum distance and the

* second value represents the parent node from which the minimum distance has been calculated

*/