|
| 1 | +package main |
| 2 | + |
| 3 | +import ( |
| 4 | + "bufio" |
| 5 | + "fmt" |
| 6 | + "log" |
| 7 | + "os" |
| 8 | + "strconv" |
| 9 | + "strings" |
| 10 | +) |
| 11 | + |
| 12 | +type graph struct { |
| 13 | + edges map[int][]*edge |
| 14 | + nodes map[int]struct{} |
| 15 | +} |
| 16 | + |
| 17 | +type edge struct { |
| 18 | + head int |
| 19 | + length int |
| 20 | +} |
| 21 | + |
| 22 | +var shortestPaths = make(map[int]int) |
| 23 | + |
| 24 | +func (g *graph) load(filename string) error { |
| 25 | + file, err := os.Open(filename) |
| 26 | + |
| 27 | + if err != nil { |
| 28 | + log.Fatal(err) |
| 29 | + } |
| 30 | + defer file.Close() |
| 31 | + |
| 32 | + scanner := bufio.NewScanner(file) |
| 33 | + for scanner.Scan() { |
| 34 | + edges := strings.Split(strings.TrimSpace(scanner.Text()), "\t") |
| 35 | + |
| 36 | + // Convert tail vertex to number |
| 37 | + tail, err := strconv.Atoi(edges[0]) |
| 38 | + if err != nil { |
| 39 | + log.Fatal(err) |
| 40 | + } |
| 41 | + |
| 42 | + g.nodes[tail] = struct{}{} |
| 43 | + |
| 44 | + for i := 1; i < len(edges); i++ { |
| 45 | + data := strings.Split(edges[i], ",") |
| 46 | + |
| 47 | + // Convert adjacent vertex to number |
| 48 | + head, err := strconv.Atoi(data[0]) |
| 49 | + if err != nil { |
| 50 | + log.Fatal(err) |
| 51 | + } |
| 52 | + |
| 53 | + // Convert length to number |
| 54 | + length, err := strconv.Atoi(data[1]) |
| 55 | + if err != nil { |
| 56 | + log.Fatal(err) |
| 57 | + } |
| 58 | + |
| 59 | + g.nodes[head] = struct{}{} |
| 60 | + g.edges[tail] = append(g.edges[tail], &edge{head: head, length: length}) |
| 61 | + } |
| 62 | + } |
| 63 | + |
| 64 | + return scanner.Err() |
| 65 | +} |
| 66 | + |
| 67 | +func (g *graph) dijkstra(source int) map[int]int { |
| 68 | + |
| 69 | + // Create map to track distances from source vertex |
| 70 | + var u int |
| 71 | + dist := make(map[int]int) |
| 72 | + |
| 73 | + // Distance from source to source is zero |
| 74 | + dist[source] = 0 |
| 75 | + |
| 76 | + // Initalize all distances to maximum |
| 77 | + for index := range g.nodes { |
| 78 | + if index != source { |
| 79 | + dist[index] = 32767 |
| 80 | + } |
| 81 | + } |
| 82 | + |
| 83 | + // Iterate over all vertices |
| 84 | + for { |
| 85 | + |
| 86 | + // Check if we have nodes left |
| 87 | + if len(g.nodes) == 0 { |
| 88 | + break |
| 89 | + } |
| 90 | + |
| 91 | + // Find vertex with minimum distance |
| 92 | + min := 32767 |
| 93 | + for index := range g.nodes { |
| 94 | + if dist[index] < min { |
| 95 | + min = dist[index] |
| 96 | + u = index |
| 97 | + } |
| 98 | + } |
| 99 | + |
| 100 | + // Remove minimum vertex |
| 101 | + delete(g.nodes, u) |
| 102 | + |
| 103 | + // Calculate minimum edgde distance |
| 104 | + for _, edge := range g.edges[u] { |
| 105 | + if dist[u]+edge.length < dist[edge.head] { |
| 106 | + dist[edge.head] = dist[u] + edge.length |
| 107 | + } |
| 108 | + } |
| 109 | + } |
| 110 | + |
| 111 | + return dist |
| 112 | +} |
| 113 | + |
| 114 | +func main() { |
| 115 | + |
| 116 | + g := &graph{} |
| 117 | + g.edges = make(map[int][]*edge) |
| 118 | + g.nodes = make(map[int]struct{}) |
| 119 | + |
| 120 | + log.Println("Loading graph...") |
| 121 | + g.load("dijkstraData.txt") |
| 122 | + |
| 123 | + distances := g.dijkstra(1) |
| 124 | + |
| 125 | + fmt.Printf("%d,%d,%d,%d,%d,%d,%d,%d,%d,%d\n", distances[7], distances[37], distances[59], distances[82], distances[99], distances[115], distances[133], distances[165], distances[188], distances[197]) |
| 126 | +} |
0 commit comments