## SOCNET@LISTS.UFL.EDU

#### View:

 Message: [ First | Previous | Next | Last ] By Topic: [ First | Previous | Next | Last ] By Author: [ First | Previous | Next | Last ] Font: Proportional Font

Subject:

Geodesics Algorithm Question

From:

Date:

Thu, 22 May 2003 09:35:30 -0400

Content-Type:

text/plain

Parts/Attachments:

 text/plain (44 lines)
 ```***** To join INSNA, visit http://www.sfu.ca/~insna/ ***** Is anyone aware of a fast (non-distributed) algorithm for all-pairs shortest path calculation? The Floyd-Warshall algorithm runs in O(3) time, so I came up with a variant of Dijkstra's algorithm that seems better than F-W (especially for sparse matrices) but still isn't particularly fast. I've included my variant pseudocode below, but I'm looking for suggestions. Thanks - Guy Given adjacency matrix A, and n= the number of vertices in A: (this converts the adjacency matrix to a distance matrix; non-adjacency is indicated by infinity, not zero) For z= 1 to n     for each row (vertex) I with outdegree>0         for each positive, non-infinite column value (edge/path), column j             for k = 1 to n (again k representing vertices with outdegree>0)                 d(i,k) = min (d(i,k), d(i,j) + d(j,k))             next         next     next     Repeat until all non-diagonal edge values in each row with outdegree>0     are less than z Next Essentially this just takes the smallest values for each column from vertices adjacent to row x. I reason the exit parameter is valid because if the algorithm only added 1 "hop" per iteration, the iteration represents a running maximum graph width. -- Guy Hagen President, Innovation Insight 27810 Sky Lake Circle - Wesley Chapel - FL 33543 813.997.2111 - innovationinsight.com _____________________________________________________________________ SOCNET is a service of INSNA, the professional association for social network researchers (http://www.sfu.ca/~insna/). To unsubscribe, send an email message to [log in to unmask] containing the line UNSUBSCRIBE SOCNET in the body of the message.```