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


Seminar Paper, 2021

15 Pages, Grade: 1.0 (A)

Anonymous


Abstract or Introduction

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.

Details

Title
Turbo Dijkstra. Finding Single-Source Shortest Paths on Planar Graphs with Nonnegative Edge Weights in Linear Time
College
University of Passau
Grade
1.0 (A)
Year
2021
Pages
15
Catalog Number
V1001013
ISBN (eBook)
9783346376480
Language
English
Tags
graph theory, planar graphs, time complexity, linear time, shortest paths, Dijkstra, optimization
Quote paper
Anonymous, 2021, Turbo Dijkstra. Finding Single-Source Shortest Paths on Planar Graphs with Nonnegative Edge Weights in Linear Time, Munich, GRIN Verlag, https://www.grin.com/document/1001013

Comments

  • No comments yet.
Read the ebook
Title: Turbo Dijkstra. Finding Single-Source Shortest Paths on Planar Graphs with Nonnegative Edge Weights in Linear Time



Upload papers

Your term paper / thesis:

- Publication as eBook and book
- High royalties for the sales
- Completely free - with ISBN
- It only takes five minutes
- Every paper finds readers

Publish now - it's free