Shortest-path tree (original) (raw)
最短路径树，是一种使用最短路径算法生成的数据结构树。
| Property | Value |
|---|---|
| dbo:abstract | In mathematics and computer science, a shortest-path tree rooted at a vertex v of a connected, undirected graph G is a spanning tree T of G, such that the path distance from root v to any other vertex u in T is the shortest path distance from v to u in G. In connected graphs where shortest paths are well-defined (i.e. where there are no negative-length cycles), we may construct a shortest-path tree using the following algorithm: 1. * Compute dist(u), the shortest-path distance from root v to vertex u in G using Dijkstra's algorithm or Bellman–Ford algorithm. 2. * For all non-root vertices u, we can assign to u a parent vertex pu such that pu is connected to u, and that dist(pu) + edge_dist(pu,u) = dist(u). In case multiple choices for pu exist, choose pu for which there exists a shortest path from v to pu with as few edges as possible; this tie-breaking rule is needed to prevent loops when there exist zero-length cycles. 3. * Construct the shortest-path tree using the edges between each node and its parent. The above algorithm guarantees the existence of shortest-path trees. Like minimum spanning trees, shortest-path trees in general are not unique. In graphs for which all edge weights are equal, shortest path trees coincide with breadth-first search trees. In graphs that have negative cycles, the set of shortest simple paths from v to all other vertices do not necessarily form a tree. For simple connected graphs, shortest-path trees can be used to suggest a non-linear relationship between two network centrality measures, closeness and degree. By assuming that the branches of the shortest-path trees are statistically similar for any root node in one network, one may show that the size of the branches depend only on the number of branches connected to the root vertex, i.e. to the degree of the root node. From this one deduces that the inverse of closeness, a length scale associated with each vertex, varies approximately linearly with the logarithm of degree. The relationship is not exact but it captures a correlation between closeness and degree in large number of networks constructed from real data and this success suggests that shortest-path trees can be a useful approximation in network analysis. (en) L'albero dei cammini minimi di uno specifico vertice di un grafo pesato , è un sottografo e un albero i cui vertici sono tutti quelli raggiungibili da in e gli archi sono ridotti in modo che l'unico cammino presente tra e un qualsiasi altro nodo del grafo sia il cammino minimo. Se il grafo è connesso l'albero dei cammini minimi è un sottografo ricoprente. L'albero dei cammini minimi ha spesso i nodi etichettati (labelled) con il costo complessivo del cammino minimo per giungere a tale nodo partendo dal nodo radice . L'albero dei cammini minimi è spesso generato dagli algoritmi di ricerca dei cammini minimi come supporto anche nel caso in cui sia richiesto un solo cammino minimo tra due nodi specifici. (it) 最短路径树，是一种使用最短路径算法生成的数据结构树。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Shortestpathtreeexample.svg?width=300 |
| dbo:wikiPageID | 9521209 (xsd:integer) |
| dbo:wikiPageLength | 3715 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1102429773 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Bellman–Ford_algorithm dbc:Spanning_tree dbr:Undirected_graph dbr:Degree_(graph_theory) dbr:Connected_graph dbr:Mathematics dbr:Shortest_path dbr:Shortest_path_problem dbr:Closeness_centrality dbr:Computer_science dbr:Spanning_tree dbr:Breadth-first_search dbr:Centrality dbr:Graph_theory dbr:Dijkstra's_algorithm dbr:Minimum_spanning_tree dbr:Vertex_(graph_theory) dbr:File:Shortestpathtreeexample.svg |
| dbp:wikiPageUsesTemplate | dbt:Cite_book dbt:Combin-stub dbt:Reflist |
| dct:subject | dbc:Spanning_tree |
| gold:hypernym | dbr:T |
| rdf:type | dbo:MartialArtist |
| rdfs:comment | 最短路径树，是一种使用最短路径算法生成的数据结构树。 (zh) In mathematics and computer science, a shortest-path tree rooted at a vertex v of a connected, undirected graph G is a spanning tree T of G, such that the path distance from root v to any other vertex u in T is the shortest path distance from v to u in G. In connected graphs where shortest paths are well-defined (i.e. where there are no negative-length cycles), we may construct a shortest-path tree using the following algorithm: The above algorithm guarantees the existence of shortest-path trees. Like minimum spanning trees, shortest-path trees in general are not unique. (en) L'albero dei cammini minimi di uno specifico vertice di un grafo pesato , è un sottografo e un albero i cui vertici sono tutti quelli raggiungibili da in e gli archi sono ridotti in modo che l'unico cammino presente tra e un qualsiasi altro nodo del grafo sia il cammino minimo. Se il grafo è connesso l'albero dei cammini minimi è un sottografo ricoprente. L'albero dei cammini minimi ha spesso i nodi etichettati (labelled) con il costo complessivo del cammino minimo per giungere a tale nodo partendo dal nodo radice . (it) |
| rdfs:label | Albero dei cammini minimi (it) Shortest-path tree (en) 最短路徑樹 (zh) |
| owl:sameAs | freebase:Shortest-path tree wikidata:Shortest-path tree dbpedia-fa:Shortest-path tree dbpedia-it:Shortest-path tree dbpedia-th:Shortest-path tree dbpedia-zh:Shortest-path tree https://global.dbpedia.org/id/4ZXjr |
| prov:wasDerivedFrom | wikipedia-en:Shortest-path_tree?oldid=1102429773&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Shortestpathtreeexample.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Shortest-path_tree |
| is dbo:wikiPageDisambiguates of | dbr:SPT |
| is dbo:wikiPageRedirects of | dbr:Shortest_path_tree |
| is dbo:wikiPageWikiLink of | dbr:Closeness_centrality dbr:Combinatorial_optimization dbr:Floyd–Warshall_algorithm dbr:Isochrone_map dbr:Dijkstra's_algorithm dbr:Open_Shortest_Path_First dbr:SPT dbr:Shortest_path_tree |
| is foaf:primaryTopic of | wikipedia-en:Shortest-path_tree |
