Ok.
When I was doing this earlier, I used the shapefiles with only single projection system.
Now, I have used the roadway lengths and travel times to compute the short paths. For this I projected the roadway shapefiles. So, now I have shapefiles with GCS_WGS_1984 and NAD_1983_UTM_Zone_17N projection systems.
Do you think this is causing the issue? Further, how can I rebuild the spatial index? I have tried to re-build the spatial index for the projected shapefiles but could not find a recalculate button to re-build the spatial index.