1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81
| package main
import ( "fmt" "math" )
const INF = math.MaxInt32
func dijkstra(graph [][]int, start, end int) ([]int, []int) { numVertices := len(graph) distances := make([]int, numVertices) visited := make([]bool, numVertices) parents := make([]int, numVertices)
for i := range distances { distances[i] = INF parents[i] = -1 } distances[start] = 0
for !visited[end] { min := INF minIndex := -1 for v := 0; v < numVertices; v++ { if !visited[v] && distances[v] <= min { min = distances[v] minIndex = v } } if minIndex == -1 { break } visited[minIndex] = true for v := 0; v < numVertices; v++ { if !visited[v] && graph[minIndex][v] != INF && distances[minIndex]+graph[minIndex][v] < distances[v] { distances[v] = distances[minIndex] + graph[minIndex][v] parents[v] = minIndex } } } path := make([]int, 0) node := end for node != -1 { path = append(path, node) node = parents[node] }
i, j := 0, len(path)-1 for i < j { path[i], path[j] = path[j], path[i] i++ j-- }
return distances, path }
func main() { graph := [][]int{ {INF, 5, 2, INF}, {5, INF, 2, 3}, {2, 2, INF, 1}, {INF, 3, 1, INF}, } start := 0 end := 3 distances, path := dijkstra(graph, start, end) fmt.Println("distances:", distances) fmt.Println("parents:", path) }
|