James W. Harris

Graph Algorithms & Combinatorial  Optimization Project

The University of Iowa

Introduction

Shortest path graph algorithms are very important component of satellite image processing. Imagine of a satellite taking aerial photos of city streets and highways. Graph algorithms can identify those streets, roads and highways. A GPS device can take those images and find the shortest path from one destination to another, so the device has to perform graph search algorithms on the image, which will find the shortest path.

The device can run breadth-first search algorithm, which is one of the simplest algorithms for searching a graph. This algorithm can start at the source point and systematically search the edges to every reachable vertex. The algorithm iterates this same process on each reachable vertex to the next reachable vertex.  It uses a FIFO queue to store the vertex. The FIFO stores the reachable vertexes in the queue.

The device can run a heuristic graph search such as A* algorithm. This algorithm will only search vertexes with minimum distance from itself to the end vertex. For simplicity of this algorithm, it first establishes a priority queue, which sorts every vertex in the queue from smallest to greatest distance, so it searches the vertexes with the minimum distances first.

Breath-First-Search

A* Algorithm