How to draw polyline on google map with two different colors between two locations

Since February 15, 2017 you can change the stroke line of a polyline. From the Release Notes (emphasys mine)

This release introduces custom styling for polylines and for the outlines of polygons and circles. Change the stroke pattern from a solid line (default) to your choice of dashes, dots, and gaps. In polylines and polygons, you can specify a bevel or round joint type to replace the default fixed miter joints. You can also change the cap at each end of a polyline from a butt (default) to a square or round cap, or specify a custom bitmap to be used as the cap. The styling of stroke patterns, joint types and start/end caps is available in the full API but not in lite mode.

Take into account that you will need to use Google Play Services 10.2 or above. Thus, in your build.gradle you will need to add:

dependencies {
    compile 'com.google.android.gms:play-services-maps:10.2.0'
}

You can specify the stroke pattern of your polyline but you can't change the color, so you will need to draw a solid polyline and a dashed polypine on top of it to reach your desired pattern (take into account that you will be drawing two polylines instead of just one and this can affect the performance):

List<LatLng> latLngs = new ArrayList<>();
// Add all your LatLngs to the List

// Draw a solid green polyline
mMap.addPolyline(new PolylineOptions()
        .addAll(latLngs)
        .color(Color.GREEN));

// Draw a dashed (60px spaced) blue polyline
List<PatternItem> dashedPattern = Arrays.asList(new Dash(60), new Gap(60));
mMap.addPolyline(new PolylineOptions()
        .addAll(latLngs)
        .pattern(dashedPattern)
        .color(Color.BLUE));

The result looks like this:

You can find more information about the new styling polyline feature here.