単一始点最短経路 （重みなし）

001 #define MAX 1000
002 int size;
003 int adjMatrix[MAX][MAX]; // graph structure
004 
005 void breadthFirstSearch( int source ){
006     queue< int > Q;
007     bool visited[MAX];
008     int dist[MAX];
009     int pi[MAX];
010     
011     for ( int i = 0; i < size; i++ ) {
012         visited[i] = false;
013         dist[i] = INT_MAX;
014     }
015     int currentNode = source;
016     
017     Q.push( currentNode );
018     visited[currentNode] = true;
019     dist[currentNode] = 0;
020     pi[currentNode] = -1;
021     
022     while ( !Q.empty() ){
023         currentNode = Q.front(), Q.pop();
024         
025         for ( int nextNode = 0; nextNode < size; nextNode++ ){
026             if ( !adjMatrix[currentNode][nextNode] ) continue;
027             if ( !visited[nextNode] ){
028                 visited[nextNode] = true;
029                 dist[nextNode] = dist[currentNode] + 1;
030                 pi[nextNode] = currentNode;
031                 Q.push( nextNode );
032             }
033         }
034     }
035 }