...when I solve the OD Cost Matrix all I get are straight lines, which leads me to believe that the points and lines aren't talking to each other.
...they take a left turn onto a bridge that is actually overhead. I know that I will need to include turning policies to prevent this but I am unsure how to do it.
The article you suggested doesn't explain how to implement the elevation field.
Is there a format the data must be in?
...is the algorithm used by ArcMap Dijkstra's algorithm?