Algorithme de recherche de tous les pairs-chemins dans un graphe
Bonjour à tous,
Je voudrais savoir s'il y a quelqu'un qui peut m'expliquer l'algorithme suivant :
Given any spanning tree T of a graph G, the edges that are not in T are called the co-tree edges with respect to T.
The size of the set V is denoted by n. The size of the set E is denoted by e.
Step I: Finding a spanning tree, T, of the weighted graph, G
Initially, all nodes are inactive. The first major part of the algorithm is to find a spanning tree, T, of the underlying unweighted graph. This can be accomplished by any one of the spanning tree finding algorithms, and we use the algorithm given by Awerbuch [Awerbuch, 1987], which takes time O(n).
The spanning tree algorithm ensures every node can identify the links incident on it as either an edge in the tree T or a co-tree edge with respect to T.
Step II: Each node determines the identities of its neighbors in the graph G:
Each node must determine the identities of its neighbors in graph G. This can be accomplished by each node sending its identity along each link incident to it. The time complexity of this step is O(1). Since each link carries exactly two messages, one from each of the incident nodes to the link, the number of messages is 2e
Step III: Determination of the All-Pairs Shortest-Distance matrix D:
This step of the algorithm deals with the transmission of distance information in G along the tree edges of T.
Initially, each vertex constructs a local distance matrix that has row and column labels corresponding to the vertex and its neighbors.
Starting at each leaf node, partial distance information is transmitted along the tree edges of T. Whenever the partial distance matrix of a neighbor is received at a non-leaf node, new columns and rows are added to the partial distance matrix of that node and existing distance data is updated. When a non-leaf node receives partial distance matrix information from all but one of its neighbors, it becomes a transmitting node and sends its partial distance matrix to the neighbor from which it did not receive a partial distance matrix message.
At the end of this step, exactly one or two nodes, called the saturated node(s) of the tree, would contain Shortest-
Distance matrix, D, of the entire graph G. We will show that the time complexity of this step is O(n).
Step IV: Communicating the All-Pairs Shortest-Distance matrix D to every node:
This communication originates at the one or two nodes that are described in Step 3, and messages travel using only tree edges of T. This step has complexities of O(n) time and O(n) number of messages
Merci.
Répondre avec citation
Envoyé par bilzzbenzbilz
Partager