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
All inputs of the C16x family have Schmitt-Trigger input characteristics. These Schmitt-Triggers are intended to always provide proper internal low and high levels, even if anundefined voltage level (between TTL-VIL and TTL-VIH) is externally applied to the pin.The hysteresis of these inputs, however, is very small, and can not be properly used in anapplication to suppress signal noise, and to shape slow rising/falling input transitions.Thus, it must be taken care that rising/falling input signals pass the undefined area of theTTL-specification between VIL and VIH with a sufficient rise/fall time, as generally usualand specified for TTL components (e.g. 74LS series: gates 1V/us, clock inputs 20V/us).The effect of the implemented Schmitt-Trigger is that even if the input signal remains inthe undefined area, well defined low/high levels are generated internally. Note that allinput signals are evaluated at specific sample points (depending on the input and theperipheral function connected to it), at that signal transitions are detected if twoconsecutive samples show different levels. Thus, only the current level of an input signalat these sample points is relevant, that means, the necessary rise/fall times of the inputsignal is only dependant on the sample rate, that is the distance in time between twoconsecutive evaluation time points. If an input signal, for instance, is sampled throughsoftware every 10us, it is irrelevant, which input level would be seen between thesamples. Thus, it would be allowable for the signal to take 10us to pass through theundefined area. Due to the sample rate of 10us, it is assured that only one sample canoccur while the signal is within the undefined area, and no incorrect transition will bedetected. For inputs which are connected to a peripheral function, e.g. capture inputs, thesample rate is determined by the clock cycle of the peripheral unit. In the case of theCAPCOM unit this means a sample rate of 400ns @ 20MHz CPU clock. This requiresinput signals to pass through the undefined area within these 400ns in order to avoidmultiple capture events.For input signals, which do not provide the required rise/fall times, external circuitry mustbe used to shape the signal transitions.In the attached diagram, the effect of the sample rate is shown. The numbers 1 to 5 in thediagram represent possible sample points. Waveform a) shows the result if the inputsignal transition time through the undefined TTL-level area is less than the time distancebetween the sample points (sampling at 1, 2, 3, and 4). Waveform b) can be the result ifthe sampling is performed more than once within the undefined area (sampling at 1, 2, 5,3, and 4).Sample points:1. Evaluation of the signal clearly results in a low level2. Either a low or a high level can be sampled here. If low is sampled, no transition willbe detected. If the sample results in a high level, a transition is detected, and anappropriate action (e.g. capture) might take place.3. Evaluation here clearly results in a high level. If the previous sample 2) had alreadydetected a high, there is no change. If the previous sample 2) showed a low, atransition from low to high is detected now.
標簽：
Signal
Input
Fall
Rise
上傳時間：
2013-10-23
上傳用戶：copu
