Floyd-Warshall算法描述
1)適用范圍：
a)APSP(All Pairs Shortest Paths)
b)稠密圖效果最佳
c)邊權可正可負
2)算法描述：
a)初始化：dis[u,v]=w[u,v]
b)For k:=1 to n
For i:=1 to n
For j:=1 to n
If dis[i,j]>dis[i,k]+dis[k,j] Then
Dis[I,j]:=dis[I,k]+dis[k,j]
c)算法結束：dis即為所有點對的最短路徑矩陣
3)算法小結：此算法簡單有效，由于三重循環結構緊湊，對于稠密圖，效率要高于執行|V|次Dijkstra算法。時間復雜度O(n^3)。
考慮下列變形：如(I,j)∈E則dis[I,j]初始為1,else初始為0，這樣的Floyd算法最后的最短路徑矩陣即成為一個判斷I,j是否有通路的矩陣。更簡單的，我們可以把dis設成boolean類型，則每次可以用“dis[I,j]:=dis[I,j]or(dis[I,k]and dis[k,j])”來代替算法描述中的藍色部分，可以更直觀地得到I,j的連通情況。
標簽：
Floyd-Warshall
Shortest
Pairs
Paths
上傳時間：
2013-12-01
上傳用戶：dyctj
/****************temic*********t5557***********************************/
#include <at892051.h>
#include <string.h>
#include <intrins.h>
#include <stdio.h>
#define uchar unsigned char
#define uint unsigned int
#define ulong unsigned long
//STC12C2051AD的SFR定義
sfr WDT_CONTR = 0xe1;//stc2051的看門狗??????
/**********全局常量************/
//寫卡的命令
#define write_command0 0//寫密碼
#define write_command1 1//寫配置字
#define write_command2 2//密碼寫數據
#define write_command3 3//喚醒
#define write_command4 4//停止命令
#define TRUE 1
#define FALSE 0
#define OK 0
#define ERROR 255
//讀卡的時間參數us
#define ts_min 250//270*11.0592/12=249//取近似的整數
#define ts_max 304//330*11.0592/12=304
#define t1_min 73//90*11.0592/12=83:-10調整
#define t1_max 156//180*11.0592/12=166
#define t2_min 184//210*11.0592/12=194
#define t2_max 267//300*11.0592/12=276
//***********不采用中斷處理:采用查詢的方法讀卡時關所有中斷****************/
sbit p_U2270B_Standby = P3^5;//p_U2270B_Standby PIN=13
sbit p_U2270B_CFE = P3^3;//p_U2270B_CFE PIN=6
sbit p_U2270B_OutPut = P3^7;//p_U2270B_OutPut PIN=2
sbit wtd_sck = P1^7;//SPI總線
sbit wtd_si = P1^3;
sbit wtd_so = P1^2;
sbit iic_data = P1^2;//lcd IIC
sbit iic_clk = P1^7;
sbit led_light = P1^6;//測試綠燈
sbit led_light1 = P1^5;//測試紅燈
sbit led_light_ok = P1^1;//讀卡成功標志
sbit fengmingqi = P1^5;
/***********全局變量************************************/
uchar data Nkey_a[4] = {0xA0, 0xA1, 0xA2, 0xA3};//初始密碼
//uchar idata card_snr[4]; //配置字
uchar data bankdata[28] = {1,2,3,4,5,6,7,1,2,3,4,5,6,7,1,2,3,4,5,6,7,1,2,3,4,5,6,7}; //存儲卡上用戶數據(1-7)7*4=28
uchar data cominceptbuff[6] = {1,2,3,4,5,6};//串口接收數組ram
uchar command; //第一個命令
uchar command1;//
//uint temp;
uchar j,i;
uchar myaddr = 8;
//uchar ywqz_count,time_count; //ywqz jishu:
uchar bdata DATA;
sbit BIT0 = DATA^0;
sbit BIT1 = DATA^1;
sbit BIT2 = DATA^2;
sbit BIT3 = DATA^3;
sbit BIT4 = DATA^4;
sbit BIT5 = DATA^5;
sbit BIT6 = DATA^6;
sbit BIT7 = DATA^7;
uchar bdata DATA1;
sbit BIT10 = DATA1^0;
sbit BIT11 = DATA1^1;
sbit BIT12 = DATA1^2;
sbit BIT13 = DATA1^3;
sbit BIT14 = DATA1^4;
sbit BIT15 = DATA1^5;
sbit BIT16 = DATA1^6;
sbit BIT17 = DATA1^7;
bit i_CurrentLevel;//i_CurrentLevel BIT 00H(Saves current level of OutPut pin of U2270B)
bit timer1_end;
bit read_ok = 0;
//緩存定時值,因用同一個定時器
union HLint
{
uint W;
struct
{
uchar H;uchar L;
}
B;
};//union HLint idata a
union HLint data a;
//緩存定時值,因用同一個定時器
union HLint0
{
uint W;
struct
{
uchar H;
uchar L;
}
B;
};//union HLint idata a
union HLint0 data b;
/**********************函數原型*****************/
//讀寫操作
void f_readcard(void);//全部讀出1~7 AOR喚醒
void f_writecard(uchar x);//根據命令寫不同的內容和操作
void f_clearpassword(void);//清除密碼
void f_changepassword(void);//修改密碼
//功能子函數
void write_password(uchar data *data p);//寫初始密碼或數據
void write_block(uchar x,uchar data *data p);//不能用通用指針
void write_bit(bit x);//寫位
/*子函數區*****************************************************/
void delay_2(uint x) //延時,時間x*10us@12mhz,最小20us@12mhz
{
x--;
x--;
while(x)
{
_nop_();
_nop_();
x--;
}
_nop_();//WDT_CONTR=0X3C;不能頻繁的復位
_nop_();
}
/////////////////////////////////////////////////////////////////////
void initial(void)
{
SCON = 0x50; //串口方式1,允許接收
//SCON =0x50;
//01010000B:10位異步收發,波特率可變,SM2=0不用接收到有效停止位才RI=1,
//REN=1允許接收
TMOD = 0x21; //定時器1 定時方式2(8位),定時器0 定時方式1(16位)
TCON = 0x40; //設定時器1 允許開始計時(IT1=1)
TH1 = 0xfD; //FB 18.432MHz 9600 波特率
TL1 = 0xfD; //fd 11.0592 9600
IE = 0X90; //EA=ES=1
TR1 = 1; //啟動定時器
WDT_CONTR = 0x3c;//使能看門狗
p_U2270B_Standby = 0;//單電源
PCON = 0x00;
IP = 0x10;//uart you xian XXXPS PT1 PX1 PT0 PX0
led_light1 = 1;
led_light = 0;
p_U2270B_OutPut = 1;
}
/************************************************/
void f_readcard()//讀卡
{
EA = 0;//全關,防止影響跳變的定時器計時
WDT_CONTR = 0X3C;//喂狗
p_U2270B_CFE = 1;//
delay_2(232); //>2.5ms
/*
// aor 用喚醒功能來防碰撞
p_U2270B_CFE = 0;
delay_2(18);//start gap>150us
write_bit(1);//10=操作碼讀0頁
write_bit(0);
write_password(&bankdata[24]);//密碼block7
p_U2270B_CFE =1 ;//
delay_2(516);//編程及確認時間5.6ms
*/
WDT_CONTR = 0X3C;//喂狗
led_light = 0;
b.W = 0;
while(!(read_ok == 1))
{
//while(p_U2270B_OutPut);//等一個穩定的低電平?超時判斷?
while(!p_U2270B_OutPut);//等待上升沿的到來同步信號檢測1
TR0 = 1;
//deng xia jiang
while(p_U2270B_OutPut);//等待下降沿
TR0 = 0;
a.B.H = TH0;
a.B.L = TL0;
TH0 = TL0 = 0;
TR0 = 1;//定時器晚啟動10個周期
//同步頭
if((324 < a.W) && (a.W < 353)) ;//檢測同步信號1
else
{
TR0 = 0;
TH0 = TL0 = 0;
goto read_error;
}
//等待上升沿
while(!p_U2270B_OutPut);
TR0 = 0;
a.B.H = TH0;
a.B.L = TL0;
TH0 = TL0 = 0;
TR0 = 1;//b.N1<<=8;
if(a.B.L < 195);//0.5p
else
{
TR0 = 0;
TH0 = TL0 = 0;
goto read_error;
}
//讀0~7塊的數據
for(j = 0;j < 28;j++)
{
//uchar i;
for(i = 0;i < 16;i++)//8個位
{
//等待下降沿的到來
while(p_U2270B_OutPut);
TR0 = 0;
a.B.H = TH0;
a.B.L = TL0;
TH0 = TL0 = 0;
TR0 = 1;
if(t2_max < a.W/*)&&(a.W < t2_max)*/)//1P
{
b.W >>= 2;//先左移再賦值
b.B.L += 0xc0;
i++;
}
else if(t1_min < a.B.L/*)&&(a.B.L < t1_max)*/)//0.5p
{
b.W >>= 1;
b.B.L += 0x80;
}
else
{
TR0 = 0;
TH0 = TL0 = 0;
goto read_error;
}
i++;
while(!p_U2270B_OutPut);//上升
TR0 = 0;
a.B.H = TH0;
a.B.L = TL0;
TH0 = TL0 = 0;
TR0 = 1;
if(t2_min < a.W/*)&&(a.W < t2_max)*/)//1P
{
b.W >>= 2;
i++;
}
else if(t1_min < a.B.L/*a.W)&&(a.B.L < t1_max)*/)//0.5P
//else if(!(a.W==0))
{
b.W >>= 1;
//temp+=0x00;
//led_light1=0;led_light=1;delay_2(40000);
}
else
{
TR0 = 0;
TH0 = TL0 = 0;
goto read_error;
}
i++;
}
//取出奇位
DATA = b.B.L;
BIT13 = BIT7;
BIT12 = BIT5;
BIT11 = BIT3;
BIT10 = BIT1;
DATA = b.B.H;
BIT17 = BIT7;
BIT16 = BIT5;
BIT15 = BIT3;
BIT14 = BIT1;
bankdata[j] = DATA1;
}
read_ok = 1;//讀卡完成了
read_error:
_nop_();
}
}
/***************************************************/
void f_writecard(uchar x)//寫卡
{
p_U2270B_CFE = 1;
delay_2(232); //>2.5ms
//psw=0 standard write
if (x == write_command0)//寫密碼:初始化密碼
{
uchar i;
uchar data *data p;
p = cominceptbuff;
p_U2270B_CFE = 0;
delay_2(31);//start gap>330us
write_bit(1);//寫操作碼1:10
write_bit(0);//寫操作碼0
write_bit(0);//寫鎖定位0
for(i = 0;i < 35;i++)
{
write_bit(1);//寫數據位1
}
p_U2270B_CFE = 1;
led_light1 = 0;
led_light = 1;
delay_2(40000);//測試使用
//write_block(cominceptbuff[4],p);
p_U2270B_CFE = 1;
bankdata[20] = cominceptbuff[0];//密碼存入
bankdata[21] = cominceptbuff[1];
bankdata[22] = cominceptbuff[2];
bankdata[23] = cominceptbuff[3];
}
else if (x == write_command1)//配置卡參數:初始化
{
uchar data *data p;
p = cominceptbuff;
write_bit(1);//寫操作碼1:10
write_bit(0);//寫操作碼0
write_bit(0);//寫鎖定位0
write_block(cominceptbuff[4],p);
p_U2270B_CFE= 1;
}
//psw=1 pssword mode
else if(x == write_command2) //密碼寫數據
{
uchar data*data p;
p = &bankdata[24];
write_bit(1);//寫操作碼1:10
write_bit(0);//寫操作碼0
write_password(p);//發口令
write_bit(0);//寫鎖定位0
p = cominceptbuff;
write_block(cominceptbuff[4],p);//寫數據
}
else if(x == write_command3)//aor //喚醒
{
//cominceptbuff[1]操作碼10 X xxxxxB
uchar data *data p;
p = cominceptbuff;
write_bit(1);//10
write_bit(0);
write_password(p);//密碼
p_U2270B_CFE = 1;//此時數據不停的循環傳出
}
else //停止操作碼
{
write_bit(1);//11
write_bit(1);
p_U2270B_CFE = 1;
}
p_U2270B_CFE = 1;
delay_2(560);//5.6ms
}
/************************************/
void f_clearpassword()//清除密碼
{
uchar data *data p;
uchar i,x;
p = &bankdata[24];//原密碼
p_U2270B_CFE = 0;
delay_2(18);//start gap>150us
//操作碼10:10xxxxxxB
write_bit(1);
write_bit(0);
for(x = 0;x < 4;x++)//發原密碼
{
DATA = *(p++);
for(i = 0;i < 8;i++)
{
write_bit(BIT0);
DATA >>= 1;
}
}
write_bit(0);//鎖定位0:0
p = &cominceptbuff[0];
write_block(0x00,p);//寫新配置參數:pwd=0
//密碼無效:即清除密碼
DATA = 0x00;//停止操作碼00000000B
for(i = 0;i < 2;i++)
{
write_bit(BIT7);
DATA <<= 1;
}
p_U2270B_CFE = 1;
delay_2(560);//5.6ms
}
/*********************************/
void f_changepassword()//修改密碼
{
uchar data *data p;
uchar i,x,addr;
addr = 0x07;//block7
p = &Nkey_a[0];//原密碼
DATA = 0x80;//操作碼10:10xxxxxxB
for(i = 0;i < 2;i++)
{
write_bit(BIT7);
DATA <<= 1;
}
for(x = 0;x < 4;x++)//發原密碼
{
DATA = *(p++);
for(i = 0;i < 8;i++)
{
write_bit(BIT7);
DATA >>= 1;
}
}
write_bit(0);//鎖定位0:0
p = &cominceptbuff[0];
write_block(0x07,p);//寫新密碼
p_U2270B_CFE = 1;
bankdata[24] = cominceptbuff[0];//密碼存入
bankdata[25] = cominceptbuff[1];
bankdata[26] = cominceptbuff[2];
bankdata[27] = cominceptbuff[3];
DATA = 0x00;//停止操作碼00000000B
for(i = 0;i < 2;i++)
{
write_bit(BIT7);
DATA <<= 1;
}
p_U2270B_CFE = 1;
delay_2(560);//5.6ms
}
/***************************子函數***********************************/
void write_bit(bit x)//寫一位
{
if(x)
{
p_U2270B_CFE = 1;
delay_2(32);//448*11.0592/120=42延時448us
p_U2270B_CFE = 0;
delay_2(28);//280*11.0592/120=26寫1
}
else
{
p_U2270B_CFE = 1;
delay_2(92);//192*11.0592/120=18
p_U2270B_CFE = 0;
delay_2(28);//280*11.0592/120=26寫0
}
}
/*******************寫一個block*******************/
void write_block(uchar addr,uchar data *data p)
{
uchar i,j;
for(i = 0;i < 4;i++)//block0數據
{
DATA = *(p++);
for(j = 0;j < 8;j++)
{
write_bit(BIT0);
DATA >>= 1;
}
}
DATA = addr <<= 5;//0地址
for(i = 0;i < 3;i++)
{
write_bit(BIT7);
DATA <<= 1;
}
}
/*************************************************/
void write_password(uchar data *data p)
{
uchar i,j;
for(i = 0;i < 4;i++)//
{
DATA = *(p++);
for(j = 0;j < 8;j++)
{
write_bit(BIT0);
DATA >>= 1;
}
}
}
/*************************************************/
void main()
{
initial();
TI = RI = 0;
ES = 1;
EA = 1;
delay_2(28);
//f_readcard();
while(1)
{
f_readcard(); //讀卡
f_writecard(command1); //寫卡
f_clearpassword(); //清除密碼
f_changepassword(); //修改密碼
}
}
標簽：
12345
上傳時間：
2017-10-20
上傳用戶：my_lcs
