Finding the number of vertices within less or equal distance d of vertex x

Question

I have to use a graph traversal ( i was thinking of BST) to determine how many vertex in g are in a distance of v in less or equal to N , this is , a travel wich the distance is N ou less edges.

int succN (Grafo g, int v, int N)

I have this struct to work with :

#define MAX 100

typedef int WEIGHT;

struct edge {
   int dest;
   WEIGHT weight;
   struct edge *next;
};

typedef struct edge Edge;
typedef struct edge *GraphL[MAX];

I'm having a difficult time to make a efficient solution in c. The only way i'm seeing right now its to make a recursive call in an aux function with the BST

You could explore Dijkstra's algorithm. Depending on the loop condition, you can either find a shortest route to a target node without necessarily visiting all nodes; or visit all nodes (once) and find the shortest distance to each from the start. Both uses make an efficient algorithm. — Weather Vane, Dec 25 '16 at 17:19
@WeatherVane In this particular case the weight is 1 , there for its not a weighted graph . Can i still use Dijkstra's algorhim ? — , Dec 25 '16 at 18:06
Here is an example of [Dijkstra's algorithm](http://stackoverflow.com/questions/34256346/how-to-find-the-fastest-route-in-a-maze-in-c/34257513#34257513) in another context but the ideas will be the same. I don't usually need a *call* to explore neighbours (Dijkstra is *not* recursive) but it was convenient here. How you explore linked nodes varies with their encoding method - perhaps a linked list of connected nodes. The example finds one shortest route, but if the main loop is changed to `while(1)` and you break when `listlen == 0` you will find the distance of all nodes from the start node. — Weather Vane, Dec 25 '16 at 18:25
@DavidEisenstat i can't modify the structure unfortunately . — , Dec 25 '16 at 18:41

score 1 · Answer 1 · answered Dec 26 '16 at 13:41

If your weights are nonnegative, you can use Dijkstra algorithm Here is a simple pseudo-code. It has a O(n^2) time complexity (n = number of nodes).

ans = 0
dist[0 .. n-1, None] = {INF, ..., INF}
dist[v] = 0
iterate n times
   best = None

   for each node u
      if not seen[u] and dist[u] < dist[best]
         best = u

   if dist[best] > N
      break

   seen[best] = true
   ans++
   for each edge from best (going to v, of weight w)
      if dist[best] + w < dist[v]
         dist[v] = dist[best] + w

return ans

If all your weights are equal to 1 (as you are pointing out in comments), then a breadth-first search will be enough.

Finding the number of vertices within less or equal distance d of vertex x

1 Answers1