Shortest distance matrix using GIS

[govindaDumaru]

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.

[larryzhang]

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]

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]

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

[DanPatterson_Retired]

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]

Got it    Spanning Tree Tools  

[govindaDumaru]

Thanks a lot Dan.

[larryzhang]

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.

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

[DanPatterson_Retired]

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]

Greeting, Dan,

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