Floyd-Warshall algorithm

GSQL
#1

HI i just want to use Floyd-Warshall algorithm is there any pre defind algorithm in tiger graph .

#2

So you need a shortest-path algorithm that can handle negative edge weights?
Do you also need all-pairs?
We have 3 versions of single-source shortest path (SSSP), depending on what typical of weights you have:

  1. unweighted edge: tg_shortest_ss_no_wt (basically BFS)
  2. positive weights: tg_shortest_ss_pos_wt (NOT Dijsktra’s, because we use parallel processing)
  3. negative weights: tg_shortest_ss_any_wt (Bellman-Ford)

We do not currently have Floyd-Warshall for all-pairs AND negative weight edges. We haven’t seen many real-world use cases for negative weights, and even with the dynamic programming, it’s a fairly compute-intensive algorithm. Can I ask what is your use case?

Documentation: Pathfinding Algorithms :: TigerGraph Graph Data Science Library
Most algorithms can be installed with a few clicks from GraphStudio:
Write Queries :: GraphStudio and Admin Portal

1 Like
#3

i am designing an algo that will return all possible routes taking each vertices as a source and include all vertices in the path.

#4

You want shortest paths, right?
You haven’t actually said that in any of your posts.

Do you need to find the paths themselves, or just the length of the shortest paths?
When you saw “all possible paths”, does the “all” refer to

  1. “every starting point to every destination point” → all the possible choices of A and B.
    or
  2. “If there is more than one shortest path from A to B, I want to know all of them.” → all ways of getting from A to B.

The basic Floyd-Warshall algorithm will find you the length of the shortest paths, where “all” is sense (1). An extended version of it can find the paths themselves.

1 Like
#5

thanks for replying

  1. “If there is more than one shortest path from A to B, I want to know all of them.” → all ways of getting from A to B and store the path on vertex . including there distance .
#6

We can write an example of Floyd-Warshall is GSQL for you.
Flloyd-Warshall is O(V^3), so it is not recommended for large graphs.

Is you interest just for academic purposes, or do you have a use case?

Note that saving and returning all the paths does require steps and storage.

#7

yup i have a usecase.