Research and improvement on optimal path analysis algorithm based on cost-distance grid

Xin Zhang; Guofeng Cao; Lili Zhang

doi:10.1109/IGARSS.2006.223

Research and improvement on optimal path analysis algorithm based on cost-distance grid

Xin Zhang, Guofeng Cao, Lili Zhang

Geosciences

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

The optimal path analysis based on cost distance grid is another common path analysis method besides the network path analysis. How to improve the efficiency of generating cost distance grid is a major difficulty in this method and how to reduce the repeated calculation and comparison is the key challenge in improving the efficiency. Based on "Node/Link" model, this paper adopts the Dijkstra algorithm idea, and extends it to multiple source optimal path finding, presents an algorithm of only calculating the source cell's neighboring cells which influence the calculation of working accumulative cost distance. Besides, some optimized storage and sorting techniques are also introduced.

Original language	English
Title of host publication	2006 IEEE International Geoscience and Remote Sensing Symposium, IGARSS
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	860-862
Number of pages	3
ISBN (Print)	0780395107, 9780780395107
DOIs	https://doi.org/10.1109/IGARSS.2006.223
State	Published - 2006
Event	2006 IEEE International Geoscience and Remote Sensing Symposium, IGARSS - Denver, CO, United States Duration: Jul 31 2006 → Aug 4 2006

Publication series

Name	International Geoscience and Remote Sensing Symposium (IGARSS)

Conference

Conference	2006 IEEE International Geoscience and Remote Sensing Symposium, IGARSS
Country/Territory	United States
City	Denver, CO
Period	07/31/06 → 08/4/06

Keywords

Accumulative cost distance
Cost-distance grid
Direction grid
Optimal path Analysis

Access to Document

10.1109/IGARSS.2006.223

Cite this

Zhang, X., Cao, G., & Zhang, L. (2006). Research and improvement on optimal path analysis algorithm based on cost-distance grid. In 2006 IEEE International Geoscience and Remote Sensing Symposium, IGARSS (pp. 860-862). [4241370] (International Geoscience and Remote Sensing Symposium (IGARSS)). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/IGARSS.2006.223

@inproceedings{40071cf2598d47e3ad6eb551647dd6b1,

title = "Research and improvement on optimal path analysis algorithm based on cost-distance grid",

abstract = "The optimal path analysis based on cost distance grid is another common path analysis method besides the network path analysis. How to improve the efficiency of generating cost distance grid is a major difficulty in this method and how to reduce the repeated calculation and comparison is the key challenge in improving the efficiency. Based on {"}Node/Link{"} model, this paper adopts the Dijkstra algorithm idea, and extends it to multiple source optimal path finding, presents an algorithm of only calculating the source cell's neighboring cells which influence the calculation of working accumulative cost distance. Besides, some optimized storage and sorting techniques are also introduced.",

keywords = "Accumulative cost distance, Cost-distance grid, Direction grid, Optimal path Analysis",

author = "Xin Zhang and Guofeng Cao and Lili Zhang",

year = "2006",

doi = "10.1109/IGARSS.2006.223",

language = "English",

isbn = "0780395107",

series = "International Geoscience and Remote Sensing Symposium (IGARSS)",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "860--862",

booktitle = "2006 IEEE International Geoscience and Remote Sensing Symposium, IGARSS",

note = "2006 IEEE International Geoscience and Remote Sensing Symposium, IGARSS ; Conference date: 31-07-2006 Through 04-08-2006",

}

Zhang, X, Cao, G & Zhang, L 2006, Research and improvement on optimal path analysis algorithm based on cost-distance grid. in 2006 IEEE International Geoscience and Remote Sensing Symposium, IGARSS., 4241370, International Geoscience and Remote Sensing Symposium (IGARSS), Institute of Electrical and Electronics Engineers Inc., pp. 860-862, 2006 IEEE International Geoscience and Remote Sensing Symposium, IGARSS, Denver, CO, United States, 07/31/06. https://doi.org/10.1109/IGARSS.2006.223

Research and improvement on optimal path analysis algorithm based on cost-distance grid. / Zhang, Xin; Cao, Guofeng; Zhang, Lili.
2006 IEEE International Geoscience and Remote Sensing Symposium, IGARSS. Institute of Electrical and Electronics Engineers Inc., 2006. p. 860-862 4241370 (International Geoscience and Remote Sensing Symposium (IGARSS)).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Research and improvement on optimal path analysis algorithm based on cost-distance grid

AU - Zhang, Xin

AU - Cao, Guofeng

AU - Zhang, Lili

PY - 2006

Y1 - 2006

N2 - The optimal path analysis based on cost distance grid is another common path analysis method besides the network path analysis. How to improve the efficiency of generating cost distance grid is a major difficulty in this method and how to reduce the repeated calculation and comparison is the key challenge in improving the efficiency. Based on "Node/Link" model, this paper adopts the Dijkstra algorithm idea, and extends it to multiple source optimal path finding, presents an algorithm of only calculating the source cell's neighboring cells which influence the calculation of working accumulative cost distance. Besides, some optimized storage and sorting techniques are also introduced.

AB - The optimal path analysis based on cost distance grid is another common path analysis method besides the network path analysis. How to improve the efficiency of generating cost distance grid is a major difficulty in this method and how to reduce the repeated calculation and comparison is the key challenge in improving the efficiency. Based on "Node/Link" model, this paper adopts the Dijkstra algorithm idea, and extends it to multiple source optimal path finding, presents an algorithm of only calculating the source cell's neighboring cells which influence the calculation of working accumulative cost distance. Besides, some optimized storage and sorting techniques are also introduced.

KW - Accumulative cost distance

KW - Cost-distance grid

KW - Direction grid

KW - Optimal path Analysis

UR - http://www.scopus.com/inward/record.url?scp=34948846043&partnerID=8YFLogxK

U2 - 10.1109/IGARSS.2006.223

DO - 10.1109/IGARSS.2006.223

M3 - Conference contribution

AN - SCOPUS:34948846043

SN - 0780395107

SN - 9780780395107

T3 - International Geoscience and Remote Sensing Symposium (IGARSS)

SP - 860

EP - 862

BT - 2006 IEEE International Geoscience and Remote Sensing Symposium, IGARSS

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2006 IEEE International Geoscience and Remote Sensing Symposium, IGARSS

Y2 - 31 July 2006 through 4 August 2006

ER -

Research and improvement on optimal path analysis algorithm based on cost-distance grid

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this