Dijkstra

#include <iostream>     // std::cout
#include <set>
#include <vector>

using namespace std;

void dijkstra(vector<vector<int> > &graph, int src)
{
    int size = graph.size();

    vector<int> shortestDist;
    for (int i = 0; i < size; i++) {
        shortestDist.push_back(INT_MAX);
    }  
    shortestDist[src] = 0;
    set< pair<int, int> > active_vertices;
    active_vertices.insert(make_pair(0, src));

    while (active_vertices.size() != 0) {
        int vertex = (active_vertices.begin())->second;
        active_vertices.erase(make_pair(shortestDist[vertex], vertex));
        for (int i = 0; i < size; i++) {
            if (graph[vertex][i] != 0) {
                if ((shortestDist[vertex] + graph[vertex][i]) < shortestDist[i]) {
                    active_vertices.erase(make_pair(shortestDist[i], i));
                    shortestDist[i] = (shortestDist[vertex] + graph[vertex][i]);
                    active_vertices.insert(make_pair(shortestDist[i], i));
                }
            }
        }
    }
    for(int i = 0; i < size; i++) {
        printf("%d : %d\n", i, shortestDist[i]);
    }
}

int main()
{
   /* Let us create the example graph discussed above */
   int graph[9][9] = {{0, 4,  0, 0,   0, 0,  0, 8,  0},
                      {4, 0,  8, 0,   0, 0,  0, 11, 0},
                      {0, 8,  0, 7,   0, 4,  0, 0,  2},
                      {0, 0,  7, 0,   9, 14, 0, 0,  0},
                      {0, 0,  0, 9,   0, 10, 0, 0,  0},
                      {0, 0,  4, 14, 10, 0,  2, 0,  0},
                      {0, 0,  0, 0,   0, 2,  0, 1,  6},
                      {8, 11, 0, 0,   0, 0,  1, 0,  7},
                      {0, 0,  2, 0,   0, 0,  6, 7,  0}
                     };
 
    vector<vector<int> > input;
    for (int i = 0; i < 9; i++) {
        vector<int> temp;
        for (int j = 0; j < 9; j++) {
            temp.push_back(graph[i][j]);
        }
        input.push_back(temp);
}

    dijkstra(input, 0);
    printf("end\n");
    return 0;
}