Parallel all-pairs shortest path algorithm (original) (raw)
Parallele All-Pair-Shortest-Paths-Algorithmen sind Algorithmen in der Graphentheorie, um kürzeste Wege zwischen zwei Knoten zu finden. Die kürzesten Wege zwischen allen Knoten in einem Graphen zu finden, bezeichnet man als All-Pairs-Shortest-Path-Problem. Da bei sequentiellen Algorithmen, die dieses Problem lösen, große Graphen zu langen Laufzeiten führen, lohnt es sich diese zu parallelisieren. Hier werden Techniken zur Parallelisierung für die bekanntesten Algorithmen und deren Auswirkungen auf die Laufzeiten vorgestellt.
| Property | Value |
|---|---|
| dbo:abstract | Parallele All-Pair-Shortest-Paths-Algorithmen sind Algorithmen in der Graphentheorie, um kürzeste Wege zwischen zwei Knoten zu finden. Die kürzesten Wege zwischen allen Knoten in einem Graphen zu finden, bezeichnet man als All-Pairs-Shortest-Path-Problem. Da bei sequentiellen Algorithmen, die dieses Problem lösen, große Graphen zu langen Laufzeiten führen, lohnt es sich diese zu parallelisieren. Hier werden Techniken zur Parallelisierung für die bekanntesten Algorithmen und deren Auswirkungen auf die Laufzeiten vorgestellt. (de) A central problem in algorithmic graph theory is the shortest path problem. Hereby, the problem of finding the shortest path between every pair of nodes is known as all-pair-shortest-paths (APSP) problem. As sequential algorithms for this problem often yield long runtimes, parallelization has shown to be beneficial in this field. In this article two efficient algorithms solving this problem are introduced. Another variation of the problem is the single-source-shortest-paths (SSSP) problem, which also has parallel approaches: Parallel single-source shortest path algorithm. (en) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Apsp_dijkstra_graph.png?width=300 |
| dbo:wikiPageExternalLink | http://www.cs.cornell.edu/~bindel/class/cs5220-f11/code/path.pdf http://www.academia.edu/download/46545236/Scalability_of_parallel_algorithms_for_t20160616-15656-rc5uyt.pdf |
| dbo:wikiPageID | 56993742 (xsd:integer) |
| dbo:wikiPageLength | 17905 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1098932192 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Sequential_algorithm dbr:Shortest_path_problem dbc:Graph_algorithms dbr:Adjacency_matrix dbr:Floyd–Warshall_algorithm dbr:Graph_theory dbr:Parallel_single-source_shortest_path_algorithm dbr:Floyd_algorithm dbr:Dijkstra_algorithm dbr:File:2d_block-mapping.png dbr:File:Apsp_dijkstra_distancelist.png dbr:File:Apsp_dijkstra_graph.png dbr:File:Data-denpendencies-floyd.png dbr:Reduce-operation |
| dbp:bot | medic (en) |
| dbp:date | July 2022 (en) |
| dbp:wikiPageUsesTemplate | dbt:Cbignore dbt:Dead_link dbt:Multiple_issues dbt:No_footnotes dbt:Orphan dbt:Reflist dbt:Manual |
| dcterms:subject | dbc:Graph_algorithms |
| rdfs:comment | Parallele All-Pair-Shortest-Paths-Algorithmen sind Algorithmen in der Graphentheorie, um kürzeste Wege zwischen zwei Knoten zu finden. Die kürzesten Wege zwischen allen Knoten in einem Graphen zu finden, bezeichnet man als All-Pairs-Shortest-Path-Problem. Da bei sequentiellen Algorithmen, die dieses Problem lösen, große Graphen zu langen Laufzeiten führen, lohnt es sich diese zu parallelisieren. Hier werden Techniken zur Parallelisierung für die bekanntesten Algorithmen und deren Auswirkungen auf die Laufzeiten vorgestellt. (de) A central problem in algorithmic graph theory is the shortest path problem. Hereby, the problem of finding the shortest path between every pair of nodes is known as all-pair-shortest-paths (APSP) problem. As sequential algorithms for this problem often yield long runtimes, parallelization has shown to be beneficial in this field. In this article two efficient algorithms solving this problem are introduced. Another variation of the problem is the single-source-shortest-paths (SSSP) problem, which also has parallel approaches: Parallel single-source shortest path algorithm. (en) |
| rdfs:label | Parallele All-Pair-Shortest-Paths-Algorithmen (de) Parallel all-pairs shortest path algorithm (en) |
| owl:sameAs | wikidata:Parallel all-pairs shortest path algorithm dbpedia-de:Parallel all-pairs shortest path algorithm https://global.dbpedia.org/id/5jDXw |
| prov:wasDerivedFrom | wikipedia-en:Parallel_all-pairs_shortest_path_algorithm?oldid=1098932192&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/2d_block-mapping.png wiki-commons:Special:FilePath/Apsp_dijkstra_distancelist.png wiki-commons:Special:FilePath/Apsp_dijkstra_graph.png wiki-commons:Special:FilePath/Data-denpendencies-floyd.png |
| foaf:isPrimaryTopicOf | wikipedia-en:Parallel_all-pairs_shortest_path_algorithm |
| is dbo:wikiPageRedirects of | dbr:Parallel_All-Pair-Shortest-Paths_Algorithms |
| is dbo:wikiPageWikiLink of | dbr:Dijkstra's_algorithm dbr:Parallel_All-Pair-Shortest-Paths_Algorithms dbr:Parallel_single-source_shortest_path_algorithm |
| is foaf:primaryTopic of | wikipedia-en:Parallel_all-pairs_shortest_path_algorithm |
