Shortest Path

## Dijkstra’s Algorithm

int array[10] = {1,2,3,4,5,6,7,8,9,10}; int map[10][10]; int visit[10]; int parent[10]; int distance[10]; void Shortest_Path(int source) { int i, j, k, min, min_value; for (i = 0; i < 10; i++) { distance[i] = 0x7fffffff; } parent[source] = source; distance[source] = 0; for (i = 0; i < 10; i++) { min_value = 0x7fffffff; min = -1; for (j = 0; j < 10; j++) if (!visit[i] && distance[j] < min_value) { min_value = distance[j]; min = j; } if (min == -1) return; visit[min] = 1; for (k = 0; k < 10; k++) { if (!visit[k] && map[min][k] && distance[min] + map[min][k] < distance[k]) { // if there is no connection, map[][] = -1 distance[k] = distance[min] + map[min][k]; parent[k] = min; } } } }

## Time Complexity

Same for adjacency matrix and adjacency list

Best:

O(n) — non of the nodes are connected to each other

Avg:

O(n^{2})?

Worst:

O(n^{2}) — all nodes are connected to each other

n times { // for strong connected graph, we should do n times n times searching + n times scanning for adjacency matrix | e times scanning for adjacency list }

page revision: 7, last edited: 17 Apr 2010 04:25