MinDist in DijkstraResult for UndirectedGraph returns wrong distance for unfound dest vertex

[PauSala]

Describe the bug I would expect that minDist was Infinity if the destination node is not found, but instead, some value is returned

To Reproduce Steps to reproduce the behavior:

import { UndirectedGraph } from "data-structure-typed";  

it("Should return Infinity if dest is not found?", () => {  

  const graph = new UndirectedGraph<string>();

  for (let i = 0; i < 3; ++i) {
    graph.addVertex(graph.createVertex(i, `${i}`));
  }

  graph.addEdge(0, 1, 1);

  const dijkstraResult = graph.dijkstra(0, 2, true, true);
  expect(dijkstraResult?.minDist).toBe(Infinity);
});

Expected behavior Should DijkstraResult.minDist return Infinity when there is no path available? Maybe I am missing something.

Logs Result from logging dijkstraResult in previous test:

 DijkstraResult: {
      distMap: Map(3) {
        UndirectedVertex { key: 0, value: '0' } => 0,
        UndirectedVertex { key: 1, value: '1' } => 1,
        UndirectedVertex { key: 2, value: '2' } => Infinity
      },
      preMap: Map(2) {
        UndirectedVertex { key: 0, value: '0' } => undefined,
        UndirectedVertex { key: 1, value: '1' } => UndirectedVertex { key: 0, value: '0' }
      },
      seen: Set(2) {
        UndirectedVertex { key: 0, value: '0' },
        UndirectedVertex { key: 1, value: '1' }
      },
      paths: [
        [ [UndirectedVertex] ],
        [ [UndirectedVertex], [UndirectedVertex] ],
        [ [UndirectedVertex] ]
      ],
      minDist: 1,
      minPath: [
        UndirectedVertex { key: 0, value: '0' },
        UndirectedVertex { key: 1, value: '1' }
      ]
  }

Thanks in advance! This is a very cool library.

[zrwusa]

It might be due to the naming of parameters causing confusion.

This algorithm can be used to:

Find the shortest path between two points: The most common use of the Dijkstra algorithm is to find the shortest path between two vertices in a weighted graph. Such as route planning, network routing optimization, etc.

Find the shortest path from a single source: In addition to finding the shortest path between two specific vertices, the Dijkstra algorithm is also commonly used to find the shortest paths from one vertex (the source) to all other vertices in the graph. This is very useful for situations where you need the optimal paths from a fixed starting point to multiple destinations.

You have added three nodes 0, 1, 2, and an edge from 0 to 1. Since Dijkstra is a universal algorithm, the parameters in graph.dijkstra(0, 2, true, true) indicate that the result will be the minimum distance (minDist) to the destination vertex starting from 0, and the collection of shortest paths (paths). To find the shortest path between two points, you should use the getMinCostBetween method.

it("Should return Infinity if dest is not found?", () => {

  const graph = new UndirectedGraph<string>();

  for (let i = 0; i < 3; ++i) {
    graph.addVertex(graph.createVertex(i, `${i}`));
  }

  graph.addEdge(0, 1, 1);

  const minCostBetween = graph.getMinCostBetween(0, 2, true);
  expect(minCostBetween).toBe(Infinity);

  const minCostBetween1 = graph.getMinCostBetween(0, 1, true);
  expect(minCostBetween1).toBe(1);
});

[PauSala]

Oh I get it, Thank you!

[zrwusa]

Oh I get it, Thank you!

Please test the feature, and if there are no issues, you can close this issue.