In New Zealand being kid of human.
We might make mistakes but we will make other things too. -
Michael Joseph Savage
Published
Edited
Jun 6, 2022
1 fork
5 stars
// Driver code --- 0 means no connection
graph = [[ 0, 4, 0, 0, 0, 0, 0, 8, 0 ],
[ 4, 0, 8, 0, 0, 0, 0, 11, 0 ],
[ 0, 8, 0, 7, 0, 4, 0, 0, 2 ],
[ 0, 0, 7, 0, 9, 14, 0, 0, 0],
[ 0, 0, 0, 9, 0, 10, 0, 0, 0 ],
[ 0, 0, 4, 14, 10, 0, 2, 0, 0],
[ 0, 0, 0, 0, 0, 2, 0, 1, 6 ],
[ 8, 11, 0, 0, 0, 0, 1, 0, 7 ],
[ 0, 0, 2, 0, 0, 0, 6, 7, 0 ] ]
links = {
let con = []
for (let y = 0; y < 9; ++y) {
for (let x = 0; x < 9; ++x) {
if (graph[y][x]!= 0){
if(checkObj(con,x,y)) con.push({source:y,target:x,dist:graph[y][x]})
}
}
}
return con
}
function checkObj(arr,x,y) {
const hasAll = arr.some(d=> (d.source == x && d.target == y && d.dist == graph[y][x]))
return (arr.length === 1 && hasAll) || !hasAll
}
teGraph = ({
nodes:
[
{ id: 0 },
{ id: 1 },
{ id: 2 },
{ id: 3 },
{ id: 4 },
{ id: 5 },
{ id: 6 },
{ id: 7 },
{ id: 8 },
],
links: links
})
w = 800
height = 600
types = _.sortBy(Array.from(new Set(links.map(d => d.dist))))
V = 9 // should use array.length or something -- will refactor this later
// Function that implements Dijkstra's single source shortest path algorithm for a graph represented using adjacency matrix representation
function dijkstra(graph, src)
{
let dist = new Array(V);
let sptSet = new Array(V);
// Initialize all distances as INFINITE and stpSet[] as false
for(let i = 0; i < V; i++)
{
dist[i] = Number.MAX_VALUE;
sptSet[i] = false;
}
// Distance of source vertex from itself is always 0
dist[src] = 0;
// Find shortest path for all vertices
for(let count = 0; count < V - 1; count++)
{
// Pick the minimum distance vertex from the set of vertices not yet processed.
// u is always equal to src in first iteration.
let u = minDistance(dist, sptSet);
// Mark the picked vertex as processed
sptSet[u] = true;
// Update dist value of the adjacent vertices of the picked vertex.
for(let v = 0; v < V; v++)
{
// Update dist[v] only if is not in sptSet, there is an edge from u to v,
// and total weight of path from src to v through u is smaller than current value of dist[v]
if (!sptSet[v] && graph[u][v] != 0 &&
dist[u] != Number.MAX_VALUE &&
dist[u] + graph[u][v] < dist[v])
{
dist[v] = dist[u] + graph[u][v];
}
}
}
// Print the constructed distance array - UGLY -- will refactor this later
let out = "### Vertex -> Distance from Source<br>"
for(let i = 0; i < V; i++)
{
out = out + `.... ${i} -----> ${dist[i]} <br>`
}
return out
}
// A utility function to find the vertex with minimum distance value, from the set of vertices not yet included in shortest path tree
function minDistance(dist,sptSet)
{
// Initialize min value
let min = Number.MAX_VALUE;
let min_index = -1;
for(let v = 0; v < V; v++) // V -- will refactor this later
{
if (sptSet[v] == false && dist[v] <= min)
{
min = dist[v];
min_index = v;
}
}
return min_index;
}
import {drag, color} from "@d3/mobile-patent-suits"
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
