A O(|E|) Time Shortest Path Algorithm for Non-Negative Weighted Undirected Graphs
In most of the shortest path problems like vehicle routing problems and network routing problems, we only need an efficient path between two points—source and destination, and it is not necessary to calculate the shortest path from source to all other nodes. This paper concentrates on this very...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
2010
|
| Subjects: | |
| Online Access: | http://scholars.utp.edu.my/id/eprint/2122/ http://scholars.utp.edu.my/id/eprint/2122/1/IJCIS_2009_2.rar |
| _version_ | 1848659205439881216 |
|---|---|
| author | Qureshi, M.A. Hassan, M.F. Safdar, S. Akhbar, R. |
| author_facet | Qureshi, M.A. Hassan, M.F. Safdar, S. Akhbar, R. |
| author_sort | Qureshi, M.A. |
| building | UTP Institutional Repository |
| collection | Online Access |
| description | In most of the shortest path problems like vehicle
routing problems and network routing problems, we only need
an efficient path between two points—source and destination,
and it is not necessary to calculate the shortest path from source
to all other nodes. This paper concentrates on this very idea and
presents an algorithms for calculating shortest path for (i) nonnegative
weighted undirected graphs (ii) unweighted undirected
graphs. The algorithm completes its execution in O(|E|) for all
graphs except few in which longer path (in terms of number of
edges) from source to some node makes it best selection for that
node. |
| first_indexed | 2025-11-13T07:26:43Z |
| format | Article |
| id | oai:scholars.utp.edu.my:2122 |
| institution | Universiti Teknologi Petronas |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-13T07:26:43Z |
| publishDate | 2010 |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | oai:scholars.utp.edu.my:21222013-10-25T02:45:05Z http://scholars.utp.edu.my/id/eprint/2122/ A O(|E|) Time Shortest Path Algorithm for Non-Negative Weighted Undirected Graphs Qureshi, M.A. Hassan, M.F. Safdar, S. Akhbar, R. QA75 Electronic computers. Computer science QA76 Computer software In most of the shortest path problems like vehicle routing problems and network routing problems, we only need an efficient path between two points—source and destination, and it is not necessary to calculate the shortest path from source to all other nodes. This paper concentrates on this very idea and presents an algorithms for calculating shortest path for (i) nonnegative weighted undirected graphs (ii) unweighted undirected graphs. The algorithm completes its execution in O(|E|) for all graphs except few in which longer path (in terms of number of edges) from source to some node makes it best selection for that node. 2010 Article PeerReviewed other en cc_by http://scholars.utp.edu.my/id/eprint/2122/1/IJCIS_2009_2.rar Qureshi, M.A. and Hassan, M.F. and Safdar, S. and Akhbar, R. (2010) A O(|E|) Time Shortest Path Algorithm for Non-Negative Weighted Undirected Graphs. International Journal on Computer Science and Information Security (IJSIS), Volume 6 (No 1). pp. 40-46. ISSN 1947-5500 |
| spellingShingle | QA75 Electronic computers. Computer science QA76 Computer software Qureshi, M.A. Hassan, M.F. Safdar, S. Akhbar, R. A O(|E|) Time Shortest Path Algorithm for Non-Negative Weighted Undirected Graphs |
| title | A O(|E|) Time Shortest Path Algorithm for Non-Negative Weighted Undirected Graphs |
| title_full | A O(|E|) Time Shortest Path Algorithm for Non-Negative Weighted Undirected Graphs |
| title_fullStr | A O(|E|) Time Shortest Path Algorithm for Non-Negative Weighted Undirected Graphs |
| title_full_unstemmed | A O(|E|) Time Shortest Path Algorithm for Non-Negative Weighted Undirected Graphs |
| title_short | A O(|E|) Time Shortest Path Algorithm for Non-Negative Weighted Undirected Graphs |
| title_sort | o(|e|) time shortest path algorithm for non-negative weighted undirected graphs |
| topic | QA75 Electronic computers. Computer science QA76 Computer software |
| url | http://scholars.utp.edu.my/id/eprint/2122/ http://scholars.utp.edu.my/id/eprint/2122/1/IJCIS_2009_2.rar |