Dijkstra Algorithm

✅ Dijkstra Algorithm

weighted graph find shorest path

⭐️ Keyword

weighed graph

✅ Time complexity

Adjacent Matrix: O(N^2)
Adjacent List: O(N*logN)

✅ Code

1. array to save distance, if visited

int[] distance;
boolean visited;

1. initialize distance to max

for(int i = 1; i <= n; i++){
    distance[i] = Integer.MAX_VALUE;
}

1. initiate starting node distance, visited

distance[start] = 0;
visited[start] = true;

1. check if visited, and set distance of the node

for(int i = 1; i <= n; i++){
    if(!visited[i] && map[start][i] != 0) {
    	distance[i] = map[start][i];
    }
}

1. find the node that has not been visited, find min distance node

int min = Integer.MAX_VALUE;
int midx = -1;

for(int i = 1; i <= n; i++){
    if(!visited[i] && distance[i] != Integer.MAX_VALUE) {
    	if(distance[i] < min) {
            min = distance[i];
            midx = i;
        }
    }
}

1. check visited array, reset minimum distance with root node

visited[midx] = true;
for(int i = 1; i <= n; i++){
    if(!visited[i] && map[midx][i] != 0) {
    	if(distance[i] > distance[midx] + map[midx][i]) {
            distance[i] = distance[midx] + map[midx][i];
        }
    }
}

💡 Reference

https://soheeparklee.github.io/posts/CT-67/