It is of utmost importance for public health to identify optimal location for sensors to detect all possible contamination events. However, it has been difficult due to several reasons including the complex nature of water distribution system, inadequate technologies to detect every contaminant, and most of all, limited budget. The usual techniques for optimizing sensor locations require significant computational power and time, thus making it difficult to apply in real systems. This study simplifies the computation by utilizing network analysis, betweenness centrality, and shortest path algorithm. Betweenness centrality defines the centrality of a node in terms of degree to which the node falls on the shortest path between other pairs of nodes. In addition to network analysis, Multi-Objective Genetic Algorithm and travel time matrix are used to consider the sensitivity of flow directions in pipes, presenting Pareto solutions. Consequently, the proposed method will minimize detection time and number of sensors needed. It is expected to benefit the most when the water distribution network is large and complicated.