图论最短路之bellman-ford

[html] 
#include<stdio.h> 
#include<iostream> 
#include<string.h> 
 
using namespace std ; 
const int INF = 1000000 ; 
const int maxn = 8 ;  
int n ; 
int edge[ maxn ][ maxn ] ; 
int dist[ maxn ] ; 
int path[ maxn ] ; 
void bellman( int v0 ) 
{ 
    int i , j , k , u ; 
    for( i = 0 ; i < n ; i++ ) 
    { 
        dist[ i ] = edge[ v0 ][ i ] ; 
        if( i != v0 && dist[ i ] < INF ) 
            path[ i ] = v0 ; 
        else 
            path[ i ] = -1 ; 
    } 
    for( k = 2 ; k < n ; k++ ) 
    { 
        for( u = 0 ; u < n ; u++ ) 
        { 
            if( u != v0 ) 
            { 
                for( j = 0 ;  j < n ; j++ ) 
                { 
                    if( edge[ j ][ u ] < INF && dist[ j ] + edge[ j ][ u ] < dist[ u ] ) 
                    { 
                        dist[ u ] = dist[ j ] + edge[ j ][ u ] ; 
                        path[ u ] = j ; 
                    } 
                } 
            } 
        } 
    } 
} 
 
 
int main() 
{ 
    int i , j ; 
    int u , v , w ; 
    scanf( "%d" , &n ) ; 
    while( 1 ) 
    { 
        scanf( "%d%d%d" , &u , &v , &w ) ; 
        if( u == -1 && v == -1 && w == -1 ) 
            break ; 
        edge[ u ][ v ] = w ; 
    } 
    for( i = 0 ; i < n ; i++ ) 
    { 
        for( j = 0 ; j < n ; j++ ) 
        { 
            if( i == j ) 
                edge[ i ][ j ] = 0 ; 
            else 
                if( edge[ i ][ j ] == 0 ) 
                    edge[ i ][ j ] = INF ; 
        } 
    } 
    bellman( 0 ) ; 
    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 ] ) ; 
    }    
    return 0 ; 
} 
 
<SPAN style="FONT-FAMILY: Arial, Helvetica, sans-serif">7</SPAN> 

#include<stdio.h>
#include<iostream>
#include<string.h>

using namespace std ;
const int INF = 1000000 ;
const int maxn = 8 ;
int n ;
int edge[ maxn ][ maxn ] ;
int dist[ maxn ] ;
int path[ maxn ] ;
void bellman( int v0 )
{
 int i , j , k , u ;
 for( i = 0 ; i < n ; i++ )
 {
  dist[ i ] = edge[ v0 ][ i ] ;
  if( i != v0 && dist[ i ] < INF )
   path[ i ] = v0 ;
  else
   path[ i ] = -1 ;
 }
 for( k = 2 ; k < n ; k++ )
 {
  for( u = 0 ; u < n ; u++ )
  {
   if( u != v0 )
   {
    for( j = 0 ;  j < n ; j++ )
    {
     if( edge[ j ][ u ] < INF && dist[ j ] + edge[ j ][ u ] < dist[ u ] )
     {
      dist[ u ] = dist[ j ] + edge[ j ][ u ] ;
      path[ u ] = j ;
     }
    }
   }
  }
 }
}

int main()
{
 int i , j ;
 int u , v , w ;
 scanf( "%d" , &n ) ;
 while( 1 )
 {
  scanf( "%d%d%d" , &u , &v , &w ) ;
  if( u == -1 && v == -1 && w == -1 )
   break ;
  edge[ u ][ v ] = w ;
 }
 for( i = 0 ; i < n ; i++ )
 {
  for( j = 0 ; j < n ; j++ )
  {
   if( i == j )
    edge[ i ][ j ] = 0

补充：web前端 , HTML/CSS  ,

上一个：HTML <a> 标签的 target 属性
下一个：HTML概述