This is a related (on a lower level) to my other question. Are there any open datasets that contain latitude, longtitude, and an indicator of whether or not the point is land or water? The resolution doesn't need to be that fine (maybe 0.01 decimal degrees?).
There are some datasets that work with ocean coastlines, like the NOAA data, Natural Earth, or Landscan, but the latter is proprietary, and I don't think the first two include all water. Just oceans, from what I can tell.
If data like these are available, my plan is to create a connected graph of latitude/longitude "water cells" and use that and a shortest path algorithm to create an extremely rough estimate of distance between two points.
EDIT: I should clarify that I'm interested in a dataset that's worldwide, not just for one specific country or body of water.
.shp
format (Land polygons in the website of DIVAGIS). Both however would require some pre processing to provide what you are looking for.