Graph - Dijkstra's Algorithm

by Aaron • 10/25/2022, 8:31:50 AM

Given a graph and a source vertex in the graph, find the shortest paths from the source to all vertices in the given graph.

notion:  v --- (dis) --- v

               (8)         (7)
        2   ------  3   -------   4
      / |           | \           | \
  (4)/  |       (2) |   \         |  \  (9)
    /   |(11)       |     \  (14) |   \
  1     |      ---- 9       \     |    5
   \    |    /      |        \    |    /
(8) \   |  /(7)     |(6)  (4) \   |   / (10)
     \  | /         |           \ | /
       8 ---------  7   -------- 6
           (1)            (2)

Start: 1

step1: create records

           1    2    3     4     5     6     7     8    9
visited    T    F    F     F     F     F     F     F    F
cost       0    4   INF   INF   INF   INF   INF    8   INF
from       1    1    1     1     1     1     1     1    1

step2: find the unvisited vertex which has min cost

vertex 2

step3: update distance value of all adjacent vertices of vertex 2

matrix[from][to] = dict

3:
    record[3] = record[2] + matrix[2][3] = 4 + 8 = 12
    12 < INF => update

8:
    record[8] = record[2] + matrix[2][8] = 4 + 11 = 15
    15 > 8 => do nothing

           1    2    3     4     5     6     7     8    9
visited    T    T    F     F     F     F     F     F    F
cost       0    4    12   INF   INF   INF   INF    8   INF
from       1    1    1     1     1     1     1     1    1

loop step2, 3 till all vertex are visited

type Record struct {
 visited bool
 cost    int
 from    int
}

func Dijkstra(matrix [][]int, start int) []Record {
 num := len(matrix[0])
 records := make([]Record, num)
 for i := 0; i < num; i++ {
  records[i] = Record{
   visited: i == start,
   cost:    matrix[start][i],
   from:    start,
  }
 }

 for {
  nextNode, ok := next(records)

  if !ok {
   break
  }
  records[nextNode].visited = true

  for i := 0; i < num; i++ {
   cost := sum(records[nextNode].cost, matrix[nextNode][i])

   if cost < records[i].cost {
    records[i].cost = cost
    records[i].from = nextNode
   }
  }
 }

 return records
}

func next(records []Record) (int, bool) {
 nextNode := -1
 min := math.MaxInt
 for i := 0; i < len(records); i++ {
  if !records[i].visited && records[i].cost < min {
   min = records[i].cost
   nextNode = i
  }
 }

 return nextNode, nextNode != -1
}

func sum(a int, b int) int {
 // prevent overflow
 if a == math.MaxInt || b == math.MaxInt {
  return math.MaxInt
 }

 return a + b
}