Página de inicio >  Catálogo >  Informática - Informática teorica

Turbo Dijkstra. Finding Single-Source Shortest Paths on Planar Graphs with Nonnegative Edge Weights in Linear Time


Trabajo de Seminario, 2021

15 Páginas, Calificación: 1.0 (A)

Anonym (Autor)


Resumen o Introducción

The need to find shortest paths in a graph from some fixed source vertex to all other vertices is quite obvious and therefore one of the most important problems in graph theory. For general graphs, the standard way to go is the Dijkstra algorithm. On planar graphs, this approach takes linearithmic time in the number of vertices. However, we present an algorithm published by Henzinger et al. in 1997 that accomplishes the task in linear time on planar graphs.

Detalles

Título
Turbo Dijkstra. Finding Single-Source Shortest Paths on Planar Graphs with Nonnegative Edge Weights in Linear Time
Universidad
University of Passau
Calificación
1.0 (A)
Autor
Año
2021
Páginas
15
No. de catálogo
V1001013
ISBN (Ebook)
9783346376480
ISBN (Libro)
9783346376497
Idioma
Inglés
Palabras clave
graph theory, planar graphs, time complexity, linear time, shortest paths, Dijkstra, optimization
Citar trabajo
Anonym (Autor), 2021, Turbo Dijkstra. Finding Single-Source Shortest Paths on Planar Graphs with Nonnegative Edge Weights in Linear Time, Múnich, GRIN Verlag, https://www.grin.com/document/1001013

Comentarios

  • No hay comentarios todavía.
Leer eBook
Título: Turbo Dijkstra. Finding Single-Source Shortest Paths on Planar Graphs with Nonnegative Edge Weights in Linear Time


Textos similares


Cargar textos

Sus trabajos académicos / tesis:

- Publicación como eBook y libro impreso
- Honorarios altos para las ventas
- Totalmente gratuito y con ISBN
- Le llevará solo 5 minutos
- Cada trabajo encuentra lectores

Así es como funciona