﻿ 图论最短路之spfa-CSS_网页制作-脚本宝典

# 图论最短路之spfa

## 图论最短路之spfa

[html]#includestdio.h#includestring.h#includeiostream#includequeueusing namespace std ;const int INF = 1000000 ;const int maxn = 10 ;struct ArcNode{ int to ; int weight ...

[]
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<queue>
using namespace std ;
const int INF = 1000000 ;
const int maxn = 10 ;
struct ArcNode

int to ;
int weight ;
ArcNode *next ;
};
queue<int> Q ;
int n ;
ArcNode *List[ maxn ] ;
int inq[ maxn ]  ;
int dist[ maxn ] , path[ maxn ] ;
void SPFA( int src )

int i , u ;
ArcNode * temp ;
for( i = 0 ; i < n ; i++ )
{
dist[ i ] = INF ;
path[ i ] = src ;
inq[ i ] = 0 ;
}
dist[ src ] = 0 ;
path[ src ] = src ;
inq[ src ]++ ;
Q.push( src ) ;
while( !Q.empty() )
{
u = Q.front() ;
Q.pop() ;
inq[ u ]-- ;
temp = List[ u ] ;
while( temp != NULL )
{
int v= temp-> to ;
if( dist[ v ] > dist[ u ] + temp->weight )
{
dist[ v ] = dist[ u ] + temp -> weight ;
path[ v ] = u ;
if( !inq[ v ] )
{
Q.push( v ) ;
inq[ v ]++ ;
}
}
temp = temp -> next ;
}
}

int main()

int  i , j ;
int u , v , w ;
scanf( "%d" , &n );
memset( List , 0 , sizeof( List ) ) ;
ArcNode *temp ;
while( 1 )
{
scanf( "%d%d%d" ,&u , &v , &w ) ;
if( u == -1 && v == -1 && w == -1 )
break ;
temp = new ArcNode ;
temp -> to = v ;
temp -> weight = w;
temp -> next = NULL ;
if( List[ u ] == NULL )
List[ u ] = temp ;
else
{
temp -> next = List[ u ] ;
List[ u ] = temp ;
}
}
SPFA( 0 ) ;
for( j = 0 ; j < n ; j++ )
{
temp = List[ j ] ;
while( temp != NULL )
{
List[ j ] = temp -> next ;
delete temp ;
temp = List[ j ] ;
}
}
int shortest[ maxn ] ;
for( i = 1 ; i < n ; i++ )
{
printf( "%d\t" , dist[ i ] ) ;
memset( shortest , 0 , sizeof( shortest ) ) ;
int k = 0 ;
shortest[ k ] = i ;
while( path[ shortest[ k ] ] != 0 )
{
k++ ;
shortest[ k ] = path[ shortest[ k - 1 ] ] ;
}
k++ ;
shortest[ k ] = 0 ;
for( j = k ; j > 0 ; j-- )
printf( "%d->" , shortest[ j ] ) ;
printf( "%d\n" , shortest[ 0 ] ) ;
}

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<queue>
using namespace std ;
const int INF = 1000000 ;
const int maxn = 10 ;
struct ArcNode
{
int to ;
int weight ;
ArcNode *next ;
};
queue<int> Q ;
int n ;
ArcNode *List[ maxn ] ;
int inq[ maxn ]  ;
int dist[ maxn ] , path[ maxn ] ;
void SPFA( int src )
{
int i , u ;
ArcNode * temp ;
for( i = 0 ; i < n ; i++ )
{
dist[ i ] = INF ;
path[ i ] = src ;
inq[ i ] = 0 ;
}
dist[ src ] = 0 ;
path[ src ] = src ;
inq[ src ]++ ;
Q.push( src ) ;
while( !Q.empty() )
{
u = Q.front() ;
Q.pop() ;
inq[ u ]-- ;
temp = List[ u ] ;
while( temp != NULL )
{
int v= temp-> to ;
if( dist[ v ] > dist[ u ] + temp->weight )
{
dist[ v ] = dist[ u ] + temp -> weight ;
path[ v ] = u ;
if( !inq[ v ] )
{
Q.push( v ) ;
inq[ v ]++ ;
}
}
temp = temp -> next ;
}
}
}

int main()
{
int  i , j ;
int u , v , w ;
scanf( "%d" , &n );
memset( List , 0 , sizeof( List ) ) ;
ArcNode *temp ;
while( 1 )
{
scanf( "%d%d%d" ,&u , &v , &w ) ;
if( u == -1 && v == -1 && w == -1 )
break ;
temp = new ArcNode ;
temp -> to = v ;
temp -> weight = w;
temp -> next = NULL ;
if( List[ u ] == NULL )
List[ u ] = temp ;
else
{
temp -> next = List[ u ] ;
List[ u ] = temp ;
}
}
SPFA( 0 ) ;
for( j = 0 ; j < n ; j++ )
{
temp = List[ j ] ;
while( temp != NULL )
{
List[ j ] = temp -> next ;
delete temp ;
temp = List[ j ] ;
}
}
int shortest[ maxn ] ;
for( i = 1 ; i < n ; i++ )
{
printf( "%d\t" , dist[ i ] ) ;
memset( shortest , 0 , sizeof( shortest ) ) ;
int k = 0 ;
shortest[ k ] = i ;
while( path[ shortest[ k ] ] != 0 )
{
k++ ;
shortest[ k ] = path[ shortest[ k - 1 ] ] ;
}
k++ ;
shortest[ k ] = 0 ;
for( j = k ; j > 0 ; j-- )
printf( "%d->" , shortest[ j ] ) ;
printf( "%d\n" , shortest[ 0 ] ) ;
}
}[html]
/*

/*[html]

0 1 6
0 2 5
0 3 5
1 4 -1
2 1 -2
2 4 1
3 2 -2
3 5 -1
4 6 3
5 6 3
-1 -1 -1
1       0->3->2->1
3       0->3->2
5       0->3
0       0->3->2->1->4
4       0->3->5
3       0->3->2->1->4->6

7
0 1 6
0 2 5
0 3 5
1 4 -1
2 1 -2
2 4 1
3 2 -2
3 5 -1
4 6 3
5 6 3
-1 -1 -1
1       0->3->2->1
3       0->3->2
5       0->3
0       0->3->2->1->4
4       0->3->5
3       0->3->2->1->4->6
[html]
*/

*/

Tag：

﻿
<