FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
JavaScriptAlgorithm/Graphs/DijkstraSmallestPath.js at master · me-hasan/JavaScriptAlgorithm · GitHub
me-hasan
/
JavaScriptAlgorithm
Public
forked from
RabibHossain/JavaScriptAlgorithm
Notifications
You must be signed in to change notification settings
Fork
0
Star
0
Code
Pull requests
0
Actions
Projects
Security and quality
0
Insights
Additional navigation options
Code
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
JavaScriptAlgorithm
/
Graphs
/
DijkstraSmallestPath.js
Copy path
More file actions
More file actions
Latest commit
History
History
History
110 lines (95 loc) · 2.33 KB
Breadcrumbs
JavaScriptAlgorithm
/
Graphs
/
DijkstraSmallestPath.js
Copy path
File metadata and controls
110 lines (95 loc) · 2.33 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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
// starting at s
function
solve
(
graph
,
s
)
{
const
solutions
=
{
}
solutions
[
s
]
=
[
]
solutions
[
s
]
.
dist
=
0
while
(
true
)
{
let
p
=
null
let
neighbor
=
null
let
dist
=
Infinity
for
(
const
n
in
solutions
)
{
if
(
!
solutions
[
n
]
)
{
continue
}
const
ndist
=
solutions
[
n
]
.
dist
const
adj
=
graph
[
n
]
for
(
const
a
in
adj
)
{
if
(
solutions
[
a
]
)
{
continue
}
const
d
=
adj
[
a
]
+
ndist
if
(
d
<
dist
)
{
p
=
solutions
[
n
]
neighbor
=
a
dist
=
d
}
}
}
// no more solutions
if
(
dist
===
Infinity
)
{
break
}
// extend parent's solution path
solutions
[
neighbor
]
=
p
.
concat
(
neighbor
)
// extend parent's cost
solutions
[
neighbor
]
.
dist
=
dist
}
return
solutions
}
export
{
solve
}
// // create graph
// const graph = {}
// const layout = {
// R: ['2'],
// 2: ['3', '4'],
// 3: ['4', '6', '13'],
// 4: ['5', '8'],
// 5: ['7', '11'],
// 6: ['13', '15'],
// 7: ['10'],
// 8: ['11', '13'],
// 9: ['14'],
// 10: [],
// 11: ['12'],
// 12: [],
// 13: ['14'],
// 14: [],
// 15: []
// }
// // convert uni-directional to bi-directional graph
// let graph = {
// a: {e:1, b:1, g:3},
// b: {a:1, c:1},
// c: {b:1, d:1},
// d: {c:1, e:1},
// e: {d:1, a:1},
// f: {g:1, h:1},
// g: {a:3, f:1},
// h: {f:1}
// };
// for (const id in layout) {
// if (!graph[id]) { graph[id] = {}
}
// layout[id].forEach(function (aid) {
// graph[id][aid] = 1
// if (!graph[aid]) { graph[aid] = {}
}
// graph[aid][id] = 1
// })
// }
// // choose start node
// const start = '10'
// // get all solutions
// const solutions = solve(graph, start)
// // for s in solutions..
// ' -> ' + s + ': [' + solutions[s].join(', ') + '] (dist:' + solutions[s].dist + ')'
// From '10' to
// -> 2: [7, 5, 4, 2] (dist:4)
// -> 3: [7, 5, 4, 3] (dist:4)
// -> 4: [7, 5, 4] (dist:3)
// -> 5: [7, 5] (dist:2)
// -> 6: [7, 5, 4, 3, 6] (dist:5)
// -> 7: [7] (dist:1)
// -> 8: [7, 5, 4, 8] (dist:4)
// -> 9: [7, 5, 4, 3, 13, 14, 9] (dist:7)
// -> 10: [] (dist:0)
// -> 11: [7, 5, 11] (dist:3)
// -> 12: [7, 5, 11, 12] (dist:4)
// -> 13: [7, 5, 4, 3, 13] (dist:5)
// -> 14: [7, 5, 4, 3, 13, 14] (dist:6)
// -> 15: [7, 5, 4, 3, 6, 15] (dist:6)
// -> R: [7, 5, 4, 2, R] (dist:5)
Back
|
FazBrowse Home
|
New Git URL