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(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
}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License