FilesExpand file tree

 master

/

22_3_optimizing.js

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

45 lines (40 loc) · 1.04 KB

 master

/

22_3_optimizing.js

Copy path

Top

File metadata and controls

• Code
• Blame

45 lines (40 loc) · 1.04 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

function time(findPath) {

let graph = treeGraph(6, 6);

let startTime = Date.now();

let result = findPath(graph[0], graph[graph.length - 1]);

console.log(`Path with length ${result.length} found in ${Date.now() - startTime}ms`);

}

function findPath_set(a, b) {

let work = [[a]];

let reached = new Set([a]);

for (let path of work) {

let end = path[path.length - 1];

if (end == b) return path;

for (let next of end.edges) {

if (!reached.has(next)) {

reached.add(next);

work.push(path.concat([next]));

}

}

}

}

time(findPath_set);

function pathToArray(path) {

let result = [];

for (; path; path = path.via) result.unshift(path.at);

return result;

}

function findPath_list(a, b) {

let work = [{at: a, via: null}];

let reached = new Set([a]);

for (let path of work) {

if (path.at == b) return pathToArray(path);

for (let next of path.at.edges) {

if (!reached.has(next)) {

reached.add(next);

work.push({at: next, via: path});

}

}

}

}

time(findPath_list);