geo-shortest-path

A TypeScript library for calculating shortest paths between geographical points using Dijkstra's algorithm and Haversine distance.

Installation

npm install geo-shortest-path

Usage

Quick Usage with Main Class

import { GeoShortestPath } from 'geo-shortest-path';

// Define geographic points
const nodes = {
  A: { lat: 41.7151, lon: 44.8271 }, // Tbilisi
  B: { lat: 41.6168, lon: 41.6367 }, // Batumi
  C: { lat: 42.2662, lon: 42.7180 }, // Kutaisi
  D: { lat: 41.9945, lon: 45.0151 }, // Telavi
};

// Create object
const geoPath = new GeoShortestPath(nodes);

// Find shortest distances from Tbilisi
const distances = geoPath.findShortestDistances('A');
console.log(distances);

// Find closest point
const closest = geoPath.findClosestNode('A');
console.log(`Closest point: ${closest?.node}, distance: ${closest?.distance}m`);

// All points sorted by distance
const allSorted = geoPath.getAllNodesByDistance('A');
console.log(allSorted);

// Specific route between two points
const pathInfo = geoPath.findShortestPath('A', 'B');
console.log(`Distance: ${pathInfo.distance}m, route: ${pathInfo.path.join(' -> ')}`);

Using Individual Functions

import { 
  haversineDistance, 
  buildCompleteGraph, 
  dijkstra, 
  findClosestNode 
} from 'geo-shortest-path';

// Calculate distance between two points
const distance = haversineDistance(
  { lat: 41.7151, lon: 44.8271 }, // Tbilisi
  { lat: 41.6168, lon: 41.6367 }  // Batumi
);

// Build graph
const nodes = {
  A: { lat: 41.7151, lon: 44.8271 },
  B: { lat: 41.6168, lon: 41.6367 },
};

const graph = buildCompleteGraph(nodes);

// Dijkstra's algorithm
const distances = dijkstra(graph, 'A');
const closest = findClosestNode(distances);

Configuration

import { GeoShortestPath, DistanceConfig } from 'geo-shortest-path';

const config: DistanceConfig = {
  earthRadius: 6371000, // Earth radius in meters
  precision: 2          // Distance precision (decimal places)
};

const geoPath = new GeoShortestPath(nodes, config);

Dynamic Node Addition/Removal

const geoPath = new GeoShortestPath({});

// Add new node
geoPath.addNode('Tbilisi', 41.7151, 44.8271);
geoPath.addNode('Batumi', 41.6168, 41.6367);

// Remove node
geoPath.removeNode('Batumi');

// Get all nodes
const allNodes = geoPath.getNodes();

Custom Graph Creation

import { buildCustomGraph } from 'geo-shortest-path';

const nodes = {
  A: { lat: 41.7151, lon: 44.8271 },
  B: { lat: 41.6168, lon: 41.6367 },
  C: { lat: 42.2662, lon: 42.7180 },
};

// Only specific connections
const connections: Array<[string, string]> = [
  ['A', 'B'],
  ['B', 'C']
];

const customGraph = buildCustomGraph(nodes, connections);

API Documentation

Types

• GeoCoordinate: { lat: number, lon: number }
• GeoNodeCollection: { [nodeId: string]: GeoCoordinate }
• ShortestPathResult: { node: string, distance: number }
• DistanceConfig: { earthRadius?: number, precision?: number }

Functions

• haversineDistance(coord1, coord2, config?): Calculate distance between two points
• buildCompleteGraph(nodes, config?): Build complete graph
• buildCustomGraph(nodes, connections, config?): Build custom graph
• dijkstra(graph, startNode): Dijkstra's algorithm
• findClosestNode(distances): Find closest node

GeoShortestPath Class

Main class for unified usage of all functions.

Example: Georgian Cities

import { GeoShortestPath } from 'geo-shortest-path';

const georgianCities = {
  'Tbilisi': { lat: 41.7151, lon: 44.8271 },
  'Batumi': { lat: 41.6168, lon: 41.6367 },
  'Kutaisi': { lat: 42.2662, lon: 42.7180 },
  'Rustavi': { lat: 41.5667, lon: 44.9833 },
  'Gori': { lat: 41.9833, lon: 44.1167 },
  'Zugdidi': { lat: 42.5086, lon: 41.8708 },
  'Zestafoni': { lat: 42.1086, lon: 43.0308 },
  'Telavi': { lat: 41.9167, lon: 45.4667 },
  'Akhaltsikhe': { lat: 41.6333, lon: 43.0167 },
  'Ozurgeti': { lat: 41.9236, lon: 42.0081 }
};

const geoPath = new GeoShortestPath(georgianCities);

// Find closest city to Tbilisi
const closestToTbilisi = geoPath.findClosestNode('Tbilisi');
console.log(`Closest to Tbilisi: ${closestToTbilisi?.node}`);

// All cities by distance from Tbilisi
const citiesByDistance = geoPath.getAllNodesByDistance('Tbilisi');
citiesByDistance.forEach((city, index) => {
  console.log(`${index + 1}. ${city.node}: ${city.distance}m`);
});

License

MIT

References

• Haversine formula
• Dijkstra's algorithm