D 'Esopo | C ++ implementation for D 'Esopo-Pape algorithm ; Number of vertices in graph ; Adjacency list of graph ; Queue to store unoperated vertices ; Distance from source vertex distance = [ float ( ' inf ' ) ] * v ; Status of vertex ; let 0 be the source vertex ; Pop from front of the queue ; Scan adjacent vertices of u ; e < - [ weight , vertex ] ; if e . second is entering first time in the queue ; Append at back of queue ; Append at front of queue ; Driver Code ; Adjacency matrix of graph
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define inf  INT_MAX NEW_LINE vector < int > desopo ( vector < vector < int > > & graph ) { int v = graph . size ( ) ; map < int , vector < pair < int , int > > > adj ; for ( int i = 0 ; i < v ; i ++ ) { for ( int j = i + 1 ; j < v ; j ++ ) { if ( graph [ i ] [ j ] != 0 ) { adj [ i ] . push_back ( { graph [ i ] [ j ] , j } ) ; adj [ j ] . push_back ( { graph [ i ] [ j ] , i } ) ; } } } deque < int > q ; vector < int > distance ( v , inf ) ; vector < bool > is_in_queue ( v , false ) ; int source = 0 ; distance = 0 ; q . push_back ( source ) ; is_in_queue = true ; while ( ! q . empty ( ) ) { int u = q . front ( ) ; q . pop_front ( ) ; is_in_queue [ u ] = false ; for ( auto e : adj [ u ] ) { if ( distance [ e . second ] > distance [ u ] + e . first ) { distance [ e . second ] = distance [ u ] + e . first ; if ( ! is_in_queue [ e . second ] ) { if ( distance [ e . second ] == inf ) q . push_back ( e . second ) ; else q . push_front ( e . second ) ; is_in_queue [ e . second ] = true ; } } } } return distance ; } int main ( int argc , char const * argv [ ] ) { vector < vector < int > > graph = { { 0 , 4 , 0 , 0 , 8 } , { 0 , 0 , 8 , 0 , 11 } , { 0 , 8 , 0 , 2 , 0 } , { 0 , 0 , 2 , 0 , 1 } , { 8 , 11 , 0 , 1 , 0 } } ; for ( auto i : desopo ( graph ) ) { cout << i << " ▁ " ; } return 0 ; }