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

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

Avg:
O(n2)?

Worst:
O(n2) — 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