Graph - Dijkstra's Algorithm

by Aaron • 10/25/2022, 8:51:42 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
}