This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package main | |
import ( | |
"fmt" | |
"os" | |
"log" | |
"io/ioutil" | |
"encoding/xml" | |
) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// DijkstraFrom returns a shortest-path tree for a shortest path from u to all nodes in | |
// the graph g. If the graph does not implement Weighted, UniformCost is used. | |
// DijkstraFrom will panic if g has a u-reachable negative edge weight. | |
// | |
// If g is a graph.Graph, all nodes of the graph will be stored in the shortest-path | |
// tree, otherwise only nodes reachable from u will be stored. | |
// | |
// The time complexity of DijkstrFrom is O(|E|.log|V|). | |
func DijkstraFrom(u graph.Node, g traverse.Graph) Shortest { | |
var path Shortest |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import ( | |
"math" | |
"gonum.org/v1/gonum/graph/simple" | |
) | |
func main() { | |
self := 0 // the cost of self connection | |
absent := math.Inf(1) // the wieght returned for absent edges | |
graph := simple.NewWeightedUndirectedGraph(self, absent) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
client = { | |
0: {"name": "Client 0", "demand": 120, "covered by": [10000, 10001, 10004]}, | |
1: {"name": "Client 1", "demand": 100, "covered by": [10000]}, | |
2: {"name": "Client 2", "demand": 80, "covered by": [10002, 10003, 10004]}, | |
3: {"name": "Client 3", "demand": 140, "covered by": [10002, 10005]}, | |
4: {"name": "Client 4", "demand": 170, "covered by": [10002, 10005]}, | |
5: {"name": "Client 5", "demand": 100, "covered by": [10000, 10003]}, | |
6: {"name": "Client 6", "demand": 120, "covered by": [10002, 10003, 10004]}, | |
7: {"name": "Client 7", "demand": 90, "covered by": [10001, 10004]}, | |
8: {"name": "Client 8", "demand": 50, "covered by": [10001, 10004, 10005]}, |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
\text{Min} \quad \sum_{j \in V} x_j \\ | |
\text{s.t.} \quad \sum_{j \in V_i} x_j \geq 1 \qquad \forall i \in V \\ | |
\qquad x_j \in 0,1 \qquad \forall j \in V |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
\text{Max} \quad \sum_i \sum_j c_{ij} x_{ij} + \sum_i f_i y_i \\ | |
\text{s.t.} \quad \sum_i x_{ij} = 1 \quad \forall j \\ | |
\qquad x_{ij} \leq y_i \quad \forall i,j \\ | |
\qquad x_{ij} \geq 0 \quad \forall i,j \\ | |
\qquad y_i \in {0, 1} \quad \forall i,j |