# dijkstras-algorithm-ts

**Repository Path**: ArkTSCentralRepository/dijkstras-algorithm-ts

## Basic Information

- **Project Name**: dijkstras-algorithm-ts
- **Description**: dijkstras-algorithm-ts 是一个用 ArkTS 实现的 Dijkstra 最短路径算法，能够计算图中从起始节点到其他节点的最短路径，并返回路径的详细信息。
- **Primary Language**: Unknown
- **License**: MIT
- **Default Branch**: main
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2024-11-21
- **Last Updated**: 2024-11-23

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# dijkstras-algorithm-ts
基于[dijkstras-algorithm-ts](https://www.npmjs.com/package/dijkstras-algorithm-ts)原库1.2.0版本进行适配, 所有功能代码已经转换为`ArkTS`文件

## Install
```sh
ohpm install dijkstras-algorithm-ts
```

## Description
Dijkstra's Shortest Path Algorithm ArkTS Implementation

## goals for this project

-   study and learn about a new algorithm I didn't previously know (in this case dijkstra's shortest path algorithm) ✅
-   study it via wikipedia and youtube conceptual videos ✅
-   based off conceptual information/videos understanding write my own implementaiton without looking at others code/implementations (challenging part) ✅
-   looking at some pseudo code is allowed (though i limited that for this algorithm), but looking at others implementations is disallowed ✅
-   once algorithm is implemented, write unit tests to verify output results are correct given the graph, starting node inputs ✅
-   <em> side quest: test with multiple different graphs to be even more confident in implementation </em> ✅

## development

graph data structure representation:

```typescript
const graphA: Map<string, Map<string, number>> = {
        a: { b: 6, d: 1 },
        b: { a: 6, c: 5, e: 2, d: 2 },
        c: { b: 5, e: 5 },
        d: { a: 1, b: 2, e: 1 },
        e: { d: 1, b: 2, c: 5 },
    };
```

shortest paths results table from node a:
```typescript
const dijkstrasResultsLookUpTableFromNodeA = dijkstrasAlgorithm(
        graphA,
        "a"
    );

// output will be: 
const dijkstrasResultsLookUpTableFromNodeA: DjistraResultsTable = {
    a: { shortestDistanceFromNodeX: 0, previousVertex: null },
    b: { shortestDistanceFromNodeX: 3, previousVertex: "d" },
    c: { shortestDistanceFromNodeX: 7, previousVertex: "e" },
    d: { shortestDistanceFromNodeX: 1, previousVertex: "a" },
    e: { shortestDistanceFromNodeX: 2, previousVertex: "d" },
};
```

get shortest path to c from a:

```typescript
const path = getShortestPath(dijkstrasResultsLookUpTableFromNodeA, "c");
// output will be => ["a", "d", "e", "c"]
```

get shortest path to c from a in directional arrow formatted string:
```typescript
const pathFormattedString = getShortedPathArrowedFormattedString(path);
// output will be: "a --> d --> e --> c"
```

#### graph B tested with example code usage

graph data structure representation:

```typescript
const graphB: Map<string, Map<string, number>> = {
        a: { b: 2, d: 8 },
        b: { a: 2, e: 6, d: 5 },
        c: { f: 3, e: 9 },
        d: { a: 8, b: 5, e: 3, f: 2 },
        e: { d: 3, b: 6, c: 9, f: 1 },
        f: { d: 2, c: 3, e: 1 },
    };
```

shortest paths results table from node a:
```typescript
const dijkstrasResultsLookUpTableFromA = dijkstrasAlgorithm(graphB, "a");

// output will be:
const dijkstrasResultsLookUpTableFromA: DjistraResultsTable = {
    a: { shortestDistanceFromNodeX: 0, previousVertex: null },
    b: { shortestDistanceFromNodeX: 2, previousVertex: "a" },
    c: { shortestDistanceFromNodeX: 12, previousVertex: "f" },
    d: { shortestDistanceFromNodeX: 7, previousVertex: "b" },
    e: { shortestDistanceFromNodeX: 8, previousVertex: "b" },
    f: { shortestDistanceFromNodeX: 9, previousVertex: "d" },
};
```

get shortest path to c from a:

```typescript
const path = getShortestPath(dijkstrasResultsLookUpTableFromA, "c");
// output will be => ["a", "b", "d", "f", "c"]
```

get shortest path to c from a in directional arrow formatted string:
```typescript
const pathFormattedString = getShortedPathArrowedFormattedString(path);
// output will be: "a --> b --> d --> f --> c"
```