# Detailed explanation of the implementation of Call, Apply, and Bind in JS (source code implementation)

2023-01-25   ES

Delete the connection between point A and B, and then find the shortest circuit between the two points. If there is the shortest circuit, and the length between A and B is the minimum value, which is the shortest ring required. But I also asked for the output path. I used SPFA to find the shortest circuit and record the path.

After finishing this method, I saw that many of the short rings were found in Discuss, so I searched the Internet. It turned out that Flowd could directly find the shortest ring in the time of O (N^3), but this labeling path was a bit troublesome. In the end, he did not think of a better way to record the path, but he did find the shortest ring.

SPFA Seeking the shortest road algorithm:

View Code

```#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <queue>
#include <math.h>
#include <map>
#include <stack>
#include <vector>
#define  N 104
#define  INF 1000000000
using namespace std ;

int mp[N][N] , pre[N] , step[N] ;
int dis[N] , n , m , ans ;
bool f[N] ;
queue<int>q ;

void init()
{
memset( f , false , sizeof( f )) ;
memset( pre , -1 , sizeof ( pre )) ;
for ( int i = 0 ; i <= n ; i++ )
dis[i] = INF ;
while( !q.empty()) q.pop();
}

int Spfa( int s , int e )
{
init() ;
f[s] = true ;
dis[s] = 0 ;
q.push( s ) ;

while ( !q.empty())
{
int u = q.front() ;
q.pop();
f[u] = false ;

for ( int i = 1 ; i <= n ; i++ )
{
if ( mp[u][i] < INF && dis[i] > dis[u] + mp[u][i] )
{
dis[i] = dis[u] + mp[u][i] ;
pre[i] = u ;

if ( !f[i] )
{
f[i] = true ;
q.push( i ) ;
}
}
}
}
return dis[e] ;
}

void output( int x )
{
if ( step[x] == -1 )
return ;

output( step[x] ) ;
printf ( "%d " , step[x] ) ;
return ;
}

int main()
{
int i , j , x , y , z ;

while ( scanf ( "%d" , &n ) , n != -1 )
{
for ( i = 0 ; i <= n ; i++ )
{
for ( j = 0 ; j <= n ; j++ )
mp[i][j] = INF ;
}
scanf ( "%d" , &m ) ;
for( i = 1 ; i <= m ; i++ )
{
scanf ( "%d%d%d" , &x , &y , &z ) ;
if ( mp[x][y] > z )
mp[x][y] = mp[y][x] = z ;
}

memset( step , -1 , sizeof ( step )) ;
int pos = -1 ;
ans = INF ;
for ( i = 1 ; i <= n ; i++ )
{
for ( j = 1 ; j <= n ; j++ )
{
if ( mp[i][j] < INF )
{
z = mp[i][j] ;
mp[i][j] = mp[j][i] = INF ;
y = Spfa( j , i ) + z ;
if ( y < ans )
{
ans = y ;
pos = i ;
for ( x = 1 ; x <= n ; x++ )
step[x] = pre[x] ;
}
}
}
}
if( pos == -1 )
{
printf ( "No solution.\n" ) ;
}
else
{
output( pos ) ;
printf ( "%d\n" , pos ) ;
}
}
return 0 ;
}```

has been wa several times at the first sample. I do n’t know why, I do n’t know if it is related to the order of path output, but I change the order output of the path. Essence Essence Essence Essence Essence Essence

FLOYD seek the shortest ring (no output path)

View Code

```#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <queue>
#include <math.h>
#include <map>
#include <stack>
#include <vector>
#define  N 104
#define  INF 1000000000
using namespace std ;

int dis[N][N] , grap[N][N] ;
int n , m , ans ;
int path[N][N] ;

void output( int s , int e )
{
if ( s == e )
return ;
if ( path[s][e] == -1 )
{
printf ( " %d" , e ) ;
return ;
}
else
{
output( s , path[s][e] ) ;
output( path[s][e] , e ) ;
}
}

int main()
{
int i , j , k , x , y , z ;

while ( scanf ( "%d" , &n ) , n != -1 )
{
for ( i = 1 ; i <= n ; i++ )
{
for ( j = 1 ; j <= n ; j++ )
{
dis[i][j] = grap[i][j] = INF ;
path[i][j] = -1 ;
}
}

scanf ( "%d" , &m ) ;
for ( i = 1 ; i <= m ; i++ )
{
scanf ( "%d%d%d" , &x , &y , &z ) ;
if ( grap[x][y] > z )
{
grap[x][y] = grap[y][x] = z ;
dis[x][y] = dis[y][x] = z ;
}
}

//int s , e ;
ans = INF ;
for ( k = 1 ; k <= n ; k++ )
{
for ( i = 1 ; i < k ; i++ )
{
for ( j = 1 ; j < i ; j++ )
if( ans > dis[i][j] + grap[i][k] + grap[k][j] )
{
ans = dis[i][j] + grap[i][k] + grap[k][j] ;
//path[i][j] = k ;
//s = j ; e = i ;
}
}

for ( x = 1 ; x <= n ; x++ )
{
for ( y = 1 ; y < x ; y++ )
if( dis[x][k] + dis[k][y] < dis[x][y] )
{
dis[x][y] = dis[x][k] + dis[k][y] ;
//path[x][y] = k ;
}
}
}

if ( ans == INF )
cout<<"No solution."<<endl ;
else
{
/*i = 0 ;
int step[N] ;
for ( k = s ; k != e ; k = path[k][e] )
{
step[i++] = k ;
}
step[i++] = e ;
step[i++] = k ;

for ( j = 0 ; j < i ; j++ )
cout<<step[j]<<" ";
cout<<endl;*/
cout<<ans<<endl ;
}
}
return 0 ;
}```

Reprinted: https://www.cnblogs.com/misty1/archive/2013/01/25/2877272.html

source