Shortest distance matrix using GIS

7331
14
11-09-2014 09:52 PM
govindaDumaru
New Contributor II

Please someone tell me if we can do shortest route analysis in gis just like Djkstra's or Floyd Warshal algorithm? Actually i want to get the shortest distance matrix of network.

0 Kudos
14 Replies
larryzhang
Occasional Contributor III

govinda,

Please refer to Path Distance & associated tools  inside Distance toolset at http://resources.arcgis.com/en/help/main/10.2/index.html#/An_overview_of_the_Distance_tools/009z0000...

and ArcGIS Help (10.2, 10.2.1, and 10.2.2) 

Keep in mind that the GP tools under Distance toolset (least cost) is only used for two points (target, origin). If planning to create matrix of cost distance from more points (more targets, more origins), Python looping scripting is required….

DanPatterson_Retired
MVP Emeritus

Djkstra's Algorithm is used in the network analyst extension    which isn't free but if you are with an educational institute, you may have it.  Or there is network analysis online as well.

govindaDumaru
New Contributor II

Dear Larry Zhang and Dan Patterson

thanks for the reply. my follow up question is I have an problem of network (not all nodes are connected). I have distance in attributes for each edges (distance between nodes of network). I need to find the shortest distance matrix for all pair of nodes which I had posted above. I think cost distance matrix would help me (please comment if i am wrong). My next step is to find the minimum spanning tree (MST) from the computed cost distance matrix. Can GIS help me to find MST?

Best Regards

Govinda

0 Kudos
DanPatterson_Retired
MVP Emeritus

I posted EMST code on the scripts site but I don't have the URL here  I was called Spanning Tree tools, if you can't find it let me know and when I get to my "real" computer not this iThingy

DanPatterson_Retired
MVP Emeritus

Got it    Spanning Tree Tools  

govindaDumaru
New Contributor II

Thanks a lot Dan.

0 Kudos
larryzhang
Occasional Contributor III

Thx, Dan,


Nice works.

However, really curious on the details how ESRI implements Djkstra's Algorithm in Network Analyst for efficiency…Can you instruct?

Govinda,

For network data analysis with ArcGIS 10.x, it would be nice also to do hands-on with 'The data that the ArcGIS Network Analyst tutorial exercises and workflows reference' at http://www.arcgis.com/home/item.html?id=d6bd91b2fddc483b8ccbc66942db84cb ...which offer deep insight on how ESRI Network Analyst tackles graph data for routing questions.

After those exercises, you can build a 'network dataset' and perform analyses on a 'network dataset' (rather than SHP file) with ESRI NA, including OD cost matrix.


network-ArcGIS.JPG

By the way, please also refer to the 'Engineering Fast Route Planning Algorithms' (attachment)...

DanPatterson_Retired
MVP Emeritus

Larry... I am going on memory on the fundamentals behind NA only the NA team could elaborate.  As for the exercises, I presume that they are contained in a gdb, I usually only develop using shapefiles since I use the base python code in other open source software and gdb's add another layer of checking I don't need

larryzhang
Occasional Contributor III

Greeting, Dan,

Really nice! You are making many efforts to help others...