在MATLAB中计算有向图非相邻节点测地距离的方法咨询

Hey there! Let's break down your questions one by one, and also help you refine your approach for calculating geodesic distances between non-adjacent nodes in your directed graph.

1. Alternative Methods to Calculate Geodesic Distances #

Here are a few reliable approaches depending on your graph size and structure:

• Floyd-Warshall Algorithm: Perfect for small, dense graphs (like your N=6 case). It computes all-pairs shortest paths in one pass with nested loops, no need for specialized graph objects. You’ll need to adjust your matrix initialization first (since your W uses 0 for non-adjacent nodes):

  N=6;
  W=[0,0.797944993710195,0,0,0,0;0.495326358306295,0,0.164911895411107,0,0,0;0,0.0530273831645896,0,0.00901073533222818,0,0;0,0,0.00709165683115063,0,0.438584093809830,0;0,0,0,0.397895339311598,0,0.000916573989905329;0,0,0,0,0.00104307323830613,0];
  
  % Initialize distance matrix: set non-adjacent (W=0, i≠j) to Inf, diagonal to 0
  Geo_dist = W;
  Geo_dist(Geo_dist == 0 & ~eye(N)) = Inf;
  Geo_dist(eye(N) == 1) = 0;
  
  % Floyd-Warshall core logic
  for k=1:N
      for i=1:N
          for j=1:N
              if Geo_dist(i,j) > Geo_dist(i,k) + Geo_dist(k,j)
                  Geo_dist(i,j) = Geo_dist(i,k) + Geo_dist(k,j);
              end
          end
      end
  end
  
  % Optional: Set unreachable node pairs back to 0 (matching your original code's behavior)
  Geo_dist(isinf(Geo_dist)) = 0;
  

• Dijkstra's Algorithm: This is the backbone of MATLAB’s old graphshortestpath function, ideal for sparse graphs with positive edge weights (which yours is). You could implement it manually for each source node, but built-in functions are more efficient.
• Johnson's Algorithm: A hybrid of Bellman-Ford and Dijkstra’s, optimized for large sparse graphs. Overkill for your small N=6 case, but useful if you scale up to hundreds/thousands of nodes later.

2. MATLAB Alternatives to graphshortestpath #

The graphshortestpath function has been deprecated since R2015b. The modern replacement uses MATLAB’s graph/digraph object system, which is more intuitive and efficient:

• distances: This is the best fit for your use case—it calculates all-pairs shortest paths in one call, eliminating the need for nested loops. Here’s how to adapt your code:

  N=6;
  W=[0,0.797944993710195,0,0,0,0;0.495326358306295,0,0.164911895411107,0,0,0;0,0.0530273831645896,0,0.00901073533222818,0,0;0,0,0.00709165683115063,0,0.438584093809830,0;0,0,0,0.397895339311598,0,0.000916573989905329;0,0,0,0,0.00104307323830613,0];
  
  % Create a directed graph object (critical for your asymmetric adjacency matrix)
  G = digraph(W);
  
  % Get all-pairs shortest distances in one go
  all_dist = distances(G);
  
  % Build Geo_dist per your original logic (only fill non-adjacent pairs)
  Geo_dist = zeros(N);
  for g=1:N
      for h=1:N
          if W(g,h) == 0 && g ~= h
              Geo_dist(g,h) = all_dist(g,h);
          end
      end
  end
  

  A quick heads-up: Your original code used 'directed',false in graphshortestpath, which treats the graph as undirected. Since your adjacency matrix is asymmetric (e.g., W(1,2)≠W(2,1)), you should use digraph (not graph) to preserve directed edges—otherwise, you’ll get incorrect distances for one-way paths.

• shortestpath: Use this if you only need the distance between a single pair of nodes (e.g., shortestpath(G, 1, 4)).

3. Does Converting to a Sparse Matrix Affect Results? #

Absolutely not. Sparse matrices in MATLAB are just a memory-efficient storage format for matrices with most entries as zero—they don’t alter the numerical values of non-zero entries.

The old graphshortestpath required sparse matrices because its implementation was optimized for sparse graph structures, but this didn’t change the computation logic or final results. For your small N=6 matrix, converting to sparse has almost no benefit, but for large graphs, it saves significant memory.

With the newer digraph system, you can pass either dense or sparse matrices—both will produce identical distance calculations.

内容的提问来源于stack exchange，提问作者dtr43