search

codezonediitj / pydatastructs

A python package for data structures and algorithms
https://pydatastructs.readthedocs.io/en/stable/
Other
202 stars 270 forks source link

Adding Floyd-Warshall algorithm #295

Closed ezhil-mathy closed 4 years ago

ezhil-mathy commented 4 years ago

References to other Issues or PRs or Relevant literature

Fixes #289

Brief description of what is fixed or changed

  1. Added _floyd_warshall_adjacency_list function and _floyd_warshall_adjacency_matrix function in pydatastructs.graphs.algorithms to determine the distances and predecessors for given source and target.
  2. Added shortest_path_construction function to construct the shortest path from the predecessors details determined using the function _floyd_warshall_adjacency_list or _floyd_warshall_adjacency_matrix.

Other comments

  1. The Floyd-Warshall algorithm can be applied on a graph in a way similar to that of the Bellman-Ford algorithm. Example: shortest_paths(G, 'floyd_warshall', 'V1')
  2. Small modification will be required in the shortest_paths function in order to utilize the all pair shortest path advantage of the Floyd-Warshall algorithm. The current implementation of shortest_paths function supports only the single-source shortest path nature of the Bellman-Ford algorithm.
czgdp1807 commented 4 years ago

Nice work. Could you please add the following lines below these two for testing your patch?

    _test_shortest_paths("List", 'floyd_warshall')
    _test_shortest_paths("Matrix", 'floyd_warshall')
czgdp1807 commented 4 years ago

@ezhil-mathy Would you still like to work on this PR? Please do not close this.

czgdp1807 commented 4 years ago

Closing in favour of #302