PDF Publication Title:
Text from PDF Page: 154
134 6 ⋅ software 6.4.2 Matlab performance optimizations: Dijkstra’s algorithm We now discuss performance optimizations for the implementation of Dijkstra’s single-source shortest path algorithm. This algorithm returns the shortest path distance between a source vertex and every other reachable vertex in the graph. One required assumption is that the edge distances (or weights) are non-negative. The algorithm explores the graph in a breadth-first manner based on the current shortest distance from the source. To pick the next vertex to explore, we need to find the closest vertex to the source, add or update the distance to all their neighbors to the current set of known vertices, and repeat. Finding the next vertex to explore based on the current distances can be done with the heap data structure in the previous section. Using the heap, Dijkstra’s algorithm is only a few lines of code. 1 function [d pred]=dijkstra_slow(A,u) 2 At = A’; n = size(At,1); % transpose for row access 3 d=Inf*ones(n,1); T=zeros(n,1); L=zeros(n,1); pred=zeros(1,n); % allocate heap 4 n=1; T(n)=u; L(u)=n; % n is now the size of the heap 5 % enter the main dijkstra loop 6 d(u) = 0; 7 while n>0 8 [v,n,T,L,d] = heappop(n,T,L,d); % find the closest vertex 9 % for each vertex adjacent to v, relax it 10 [si 11 for 12 13 14 15 16 17 18 19 20 21 end 22 end sj sv]=find(At(:,v)); ei=1:length(si) w=si(ei); ew=sv(ei); % relax edge (v,w,ew) if d(w)>d(v)+ew d(w)=d(v)+ew; pred(w)=v; % ei is the edge index % w is the target, ew is the edge weight % check if w is in the heap, insert if not, else update if L(w)==0, [n,T,L,d] = heapinsert(w,d(w),n,T,L,d); else [n,T,L,d] = heapupdate(w,n,T,L,d); end end Just like the previous description, we find the closest vertex and compute the distance to each neighbor. We then update the heap and continue. This function has respectable performance: load_gaimc_graph(’cs-stanford’) % 9914 by 9914 with 36854 edges (directed) A = sprand(A); rand(’state’,0); vs = ceil(size(A,1)*rand(100,1)); tic, for i=1:100, [d pred] = dijkstra_slow(A,i); end, toc Elapsed time is 10.748844 seconds. If we remove the function calls for the heap and place the function code in-line,17 then the performance improves considerably. Elapsed time is 3.459063 seconds. The critical graph operation in Dijkstra’s algorithm is accessing the out- edges of an arbitrary vertex. The approach used in the dijkstra_slow imple- mentation above is to transpose the sparse matrix and work with the Matlab matrix structure directly. For each out-edges query, this approach involves extracting a column and using the find function to get the non-zeros.18 An alternative is to convert the sparse matrix into a compressed sparse row struc- ture on every call. Using this approach, we obtain even better performance. Elapsed time is 1.052805 seconds. 17 We have omitted the source code for this case because it gets rather verbose with all the heap manipulations. 18 Recall that Matlab stores sparse matri- ces using the compressed column format [Gilbert et al., 1992] and thus we’d need to extract columns for efficiency.PDF Image | ALGORITHMS FOR PAGERANK SENSITIVITY DISSERTATION
PDF Search Title:
ALGORITHMS FOR PAGERANK SENSITIVITY DISSERTATIONOriginal File Name Searched:
gleich.pdfDIY PDF Search: Google It | Yahoo | Bing
Cruise Ship Reviews | Luxury Resort | Jet | Yacht | and Travel Tech More Info
Cruising Review Topics and Articles More Info
Software based on Filemaker for the travel industry More Info
The Burgenstock Resort: Reviews on CruisingReview website... More Info
Resort Reviews: World Class resorts... More Info
The Riffelalp Resort: Reviews on CruisingReview website... More Info
| CONTACT TEL: 608-238-6001 Email: greg@cruisingreview.com | RSS | AMP |