Abstract:
The invention relates to a method for three-dimensional presentation of a moved structure using a tomographic method, in which a plurality of projection images are recorded from different imaging angles between a start angle with a start node point and an end angle with an end node point by an imaging unit during a number of rotation passes, with three-dimensional image data being able to be reconstructed from the projection images, with the projection images being spaced by a path or an edge. For determining the three-dimensional presentation for each angle of projection only those projection images are selected which minimize the sum of the paths or weighted edges between adjacent projection angles for a gating.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
     The present application claims the benefit of a provisional patent application filed on Feb. 19, 2008, and assigned application No. 61/029,603. The present application also claims the benefit of a German application No. 10 2008 010 006.4 filed Feb. 19, 2008. Both of the applications are incorporated by reference herein in their entirety. 
    
    
     FIELD OF THE INVENTION 
     The invention relates to a method for three-dimensional presentation of a moved structure using a tomographic method. 
     BACKGROUND OF THE INVENTION 
     The invention relates to the 3D image reconstruction of dynamic objects from 2D projection images. The theory of image reconstruction demands a set of projection images of a stationary object over projection angles in the range of 200° (180°+cone angle). With a dynamic object an attempt is made to emulate a stationary object from said object. The imaging of the heart uses only the projection data that belongs to the heart phase during which the heart is practically at rest. This occurs in the end systole and in the end diastole. 
     Usually the heart phases are known from the EKG. The heart phase is specified relative to the heartbeat length between two QRS complexes (R wave) between 0 and 100%. The end systole is then located at around 30%, the end diastole at 70-90% for a heart rate of 60 bpm. 
     This is described for example in US 2008/0025590 A1 with reference to a method for temporal and three-dimensional presentation of a periodically changing structure, for example a heart, in which a number of rotation images are created. The rotation passes required are started offset by a specific angle for an identical event of the periodic process, initiated by the specified event in the EKG signal. New image series are assembled from the rotation images, with 3D image presentations able to be reconstructed for different phase areas of the period. 
     As an alternative there is the kymogram method in CT imaging, as is described by Kachelrieβ Et al. in “Kymogram detection and kymogram-correlated Image reconstruction from subsecond spiral computed tomography scans of the heart”, published in Med. Phys. 29(7), pages 1489 to 1503, July 2002. The kymogram method determines the focal point in the projection images and searches for phases with a focal point that remains the same. For the kymogram method the projection images must be complete in the transaxial direction. This however is not the case with C-arm computer tomography. 
     SUMMARY OF THE INVENTION 
     The object to be achieved by the invention is to develop the above method so that a heart phase suitable for gating can be found even without recording an EKG. 
     A plurality of projection images are recorded from different imaging angles between a start angle with a start node point and an end angle with an end node point by an imaging unit during a number of rotation passes. Three-dimensional image data is able to be reconstructed from the projection images. The projection images are spaced by a path or an edge. 
     The object is inventively achieved, for determining the three-dimensional presentation, by selecting only those projection images for each projection angle which minimize the sum of the paths or weighted edges between adjacent projection angles for a gating. 
     It has proved advantageous if, for three-dimensional presentation of each projection angle with node point, only that projection image is selected in which among the set of the possible paths or edges the sum of the paths or weighted edges between adjacent node points possesses the lowest measure of distance. 
     Inventively the method can have the following steps:
     a) Recording the image data by a number of rotation passes,   b) Preprocessing the image data recorded,   c) Determining the average heart rate,   d) Measuring the distances of the heart rates from the average heart rate,   e) Determining edge weights,   f) Determining the projections along of the shortest path or edge between the start node point and the end node point,   g) Reconstructing the 3D data set and   h) Presenting the 3D data set.   

     Advantageously the average heart rate can be computed in an image-oriented manner, with it being determined in accordance with step c) and e) using the Euclidean distance method. 
     Inventively the shortest distance of the paths in accordance with steps e) and f) can be determined using the Dijkstra algorithm. 
     It has proved advantageous for the preprocessing in accordance with step b) to contain the following steps:
     S 1  Preprocessing of 3D reconstruction algorithms,   S 2  Reduction of the image data,   S 3  Lowpass filtering,   S 4  Computing the size of the image gradient (optional) and/or   S 5  Formation of a Region Of Interest (ROI).   

     In this case the step S 1  can inventively include x-ray scatter correction, beam hardening correction, truncation correction, overradiation correction, a correction of the low frequency drop and/or a correction of the ring artifacts. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The invention is explained below in greater detail on the basis of the exemplary embodiments shown in the drawing. The figures are as follows: 
         FIG. 1  a known x-ray C-arm system for carrying out the inventive method, 
         FIG. 2  a view of the track of a detector and a radiographic source in accordance with  FIG. 1  around an object to be examined in the axial direction of view, 
         FIG. 3  a diagram of a projection graph for a rotation image recorded by means of the x-ray C-arm system in accordance with  FIG. 1 , 
         FIG. 4  a diagram of the relative heart phase of a forwards/backwards pass, 
         FIG. 5  the normalized curves of the phase distance between EKG-based heart phases of a forwards/backwards pass and the image-based distance value 
         FIG. 6  a flowchart of the inventive method and 
         FIG. 7  a flowchart of an inventive preprocessing method. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     US 2006/0120507 A1 discloses this type of x-ray diagnostic device for executing the method for angiography which is shown for example in  FIG. 1 , which features a C-arm  2  supported to allow it to rotate on a stand  1 , at the ends of which an x-ray radiation source, for example an x-ray emitter  3 , and an x-ray image detector  4  are arranged. 
     The x-ray image detector  4  can be a rectangular or square flat semiconductor detector, which is preferably made of amorphous silicon (a-Si). 
     In the optical path of the x-ray tube assembly  3  is a patient support table  5  for recording images, of a heart of a patient to be examined for example. Connected to the x-ray diagnostic device is an imaging system  6  which receives and processes the image signals of the x-ray image detector  4 . The x-ray images can then be viewed on a monitor  7 . 
     If 3D data sets are to be created, the rotatably-supported C-arm  2  with x-ray source  3  and x-ray detector  4  is turned so that, as shown schematically in  FIG. 2  looking down from above on the axis of rotation, the x-ray source  3  depicted in this diagram by its beam focus  3  as well as the x-ray image detector  4  move on a planetary track  8  around an object  9  to be examined. The planetary track  8  can be followed completely or partly for creating a 3D data set. 
     The object  9  to be examined can for example be the body of an animal or a human being, but can also be a phantom body. 
     The x-ray source  3  emits a ray bundle  10  emanating from the ray focus of its radiographic source, which hits the x-ray image detector  4 . 
     The x-ray source  3  and the x-ray image detector  4  thus each circulate around the object  5 , so that the x—ray source  3  and the x-ray image detector  4  lie on opposite sides of the object  9  in relation to each other. 
     In normal radiography or fluoroscopy using such an x-ray diagnostic device the medical 2D data of the x-ray image detector  4  will be buffered in the imaging system  6  if necessary and subsequently reproduced on the monitor  7 . 
     Generally a gating is a selection of projection images. In the present case exactly one projection image is selected for each recorded image position, so that from a number of data sets a complete data set is obtained for a reconstruction. 
     Image guidance during interventional heart examinations using a cardio C-arm CT-system is desirable for many methods. The application of electrocardiogram gating during the acquisition of multiple, serial, backwards and forwards EKG-triggered rotation passes using a C-arm system allows the 3D+t reconstruction of the heart. The process of retrospective gating is an especially important component of 3D reconstruction. It allows the creation of a projection data set of the heart in a quasi-static state. The gold standard in gating is EKG-based. The EKG signal measures the electrical activity during of the heart cycle which can be correlated with a heart phase. The correlation between EKG-based and the actual heart state (heart geometry, blood volume, etc.) is very good and reliable for resting and regular heartbeats. With variable, high or abnormal heart rhythms, as frequently occur in a clinical environment, the correlation will be weaker. Therefore alternate gating methods must be sought which are based on the acquired projection data. In addition said methods can also take account of non-heart movements, such as the breathing for example, which are not accessible via the EKG. The object of the invention is to provide an image-based gating method without EKG which can utilize the already acquired projection data of a multiple rotation pass for a reconstruction. 
     The gating problem is represented by a weighted and directed graph of which the elements are the projection images. Each path in this graph corresponds to a possible gating. In this approach a shortest path is sought which optimizes a target function. The path outlay (weighting) is defined by similarities of projection images based on image dimensions. The optimization is additionally regulated to give preference to solutions in which consecutive selected projections are short along a C-arm pass recorded forwards or backwards. This regulation depends on an estimated average heart rate which has likewise been estimated during the image-based method. It can be shown that the introduced image-based gating method is an alternative to EKG gating. 
     For the present method it is assumed that no EKG signal is present and the recorded projection data has already been preprocessed, as will be described in greater detail below. Thus for example intensity variations, triggered by possible illumination controls, can have been corrected. Possible procedural sequences are for example sampling with multiple rotation passes of 6×4s or 4×4s, which for example produce six or four consecutive forwards and backwards passes of respectively approximately four seconds and approximately K=191 projections p i  per pass. However other procedural sequences for recording the necessary data are likewise possible. 
     The forming or formulation of image-based gating is undertaken using the following intuitive observation. 
     For the sake of simplicity only two random 2D projections p 1  and p 2  are observed from two consecutive projection directions vi (for example p 1  ε V i , p 2  ε V i+1 . The change of the image content between p 1  and p 2  is relatively small, compared to all projections from every other direction of projection. Therefore the definition of a meaningful distance value d(p 1 , p 2 ) is desirable. The computation of this distance value d(p 1 , p 2 ) is preprocessed for each projection in a number of steps. The processing steps can include: Lowpass filtering, selection of a Region of Interest (ROI) around the heart (usually the heart is centered in the projection), a local contrast enhancement or a gradient computation. Different distance functions, such as for example the sum of the quadratic difference or the correlation coefficient, are conceivable. In the present case a structure-based correlation is undertaken which provides safe results and is quick to compute. The sinogram movement (image change by detector rotation) between such consecutive projections p 1  ε V i  and p 2  ε V i+1  (inter view) is very small and a sinogram movement between two projections of the same image angle (intra view), for example p l  ε V i  and p k  ε V i+1  is not present (ignoring narrow transformations brought about by calibration). 
     This enables the definition of a distance value which is independent of angle to be avoided, which is a far greater problem. The projection pairs characterize the most similar heart phases if d is especially small. This idea can be expanded in order to cover all K available projection directions. Let a random set p 1 , . . . , p k  of projections be recorded from consecutive projection directions V 1 , . . . , V k . The degree of dissimilarity d is the sum of all d(p i , p i+1 ) for each consecutive pair of projection directions. Each possible set of projections represents a possible gating. A gating is sought which minimizes {circumflex over (d)}, so that theoretically the image data set is obtained which has the most similar heart phases which are contained in the data record. An efficient computation scheme for the minimization problem can be achieved by a vector representation of the ideas presented in a directed, weighted graph G=(U, E). The set of node points U contains all possible projection images and an additional start node point α and end node point ζ. The set of edges E contains an edge of all projection pairs from consecutive projection directions; edges from start node point α to the projection of V 1  and edges from the projection v k  to the end node point ζ. Each edge is weighted by d(p 1 , p 2 ) if the linked node points are projection images, or a constant c, if p 1 =α or p 2 =ζ. For a given projection graph G the optimum gating corresponds to the projection along the shortest path from the start node point α and the end node point ζ. 
       FIG. 3  shows a very narrow projection graph without weighting. It is similar to an acquisition method of three short rotation passes  13  (p i ) over four projection angles  14  (V i ). The arrows shown in the projection graph represent possible paths between the individual node points. The dashed-line paths  16  give an example for a possible gating in the projection graph shown which was determined on the basis of determining the shortest path  16 . 
     In addition a regulation of a subpath length is introduced in order to prevent a consecutive subpath of the same pass becoming too long. While the time distance between consecutive recorded projections is known the subpath length can be limited in accordance with the time. Therefore an additional outlay of a path is added if consecutive parts of a selected path along the same pass exceed a certain part of a predicted average heartbeat duration. In order to obtain the average heart rate based on images, the following method is employed: 
     A forwards pass is observed in which the C-arm rotates from an angle  1  . . . N and pauses for a certain time. Then the backwards pass is started and projection images are now collected in the reverse arrangement of the angles N . . . 1. If the heart phase distances are now considered at each angle  1  . . . N over time, a number of minimum values are produced, which are shown in  FIG. 5 . The forwards pass  17  is identified by the crosses x and the backwards pass  18  by the dots •. In  FIG. 4  the lines of the forwards and backwards passes cross. Evidently these minimum values correspond to crossing points of the heart phase; for example both images show the same heart phase. Luckily this situation can be exploited by an image-based algorithm which only determines the distance between image projection pairs of the same angulation. With a predetermined set of minimum values between all combinations of the Intra-projection direction of forwards and backwards passes as reference, an optimization procedure can be started. It demands an artificial heart signal over the duration of the recording which corresponds to the set of minimum reference values. The optimization is undertaken in a two-step method in order to reduce the search area. First a constant heart rate is assumed and a graphic presentation of the angulation produced is shown in  FIG. 5  which makes possible a comparison of the temporal position of the crossing points with the minimum value of the image-based similarities. Subsequently each heartbeat duration is modified in a stochastic gradient decrease by modification of the heart signal until a minimal temporal distance of all heartbeats between all forwards/backwards passes produces crossings. 
     The change of the image content for adjacent C-arm angulations is made up of the image changes as a result of the detector rotation (sinogram movement) and the changes in the heart phase. Between adjacent angles of view the distribution of the sinogram movement is to be viewed as constant and is therefore independent of the C-arm passes  1  to K. By contrast the heart phase depends on the individual pass. In each pass the object to be examined is likely to be in a different heart phase. Therefore it can be deduced from this that the similarity between consecutive C-arm angulations should have been minimized, so that the images represent the same physiological heart phase. 
     These considerations lead to the following algorithm: 
     Find a gating for the sum of the image-based distances d between adjacent projection directions in accordance with the following equation: 
     
       
         
           
             
               G 
               IB 
             
             = 
             
               
                 arg 
                 
                   ( 
                   
                     
                       g 
                       1 
                     
                     , 
                     … 
                     ⁢ 
                     
                         
                     
                     , 
                     
                       g 
                       N 
                     
                   
                   ) 
                 
                 min 
               
               ⁢ 
               
                 
                   ∑ 
                   
                     n 
                     = 
                     1 
                   
                   
                     N 
                     - 
                     1 
                   
                 
                 ⁢ 
                 
                   d 
                   ⁡ 
                   
                     ( 
                     
                       
                         p 
                         n 
                         
                           g 
                           n 
                         
                       
                       , 
                       
                         p 
                         
                           n 
                           + 
                           1 
                         
                         
                           g 
                           
                             n 
                             + 
                             1 
                           
                         
                       
                     
                     ) 
                   
                 
               
             
           
         
       
     
     This formulation can also be interpreted in one term; reduce the sum of the first gradient of the heart movement which is close to zero and represents the same heart phase. This object can easily be achieved by mapping the minimization tasks as follows onto a directed graph which is called the projection graph G=(V, E): 
     The set of node points contains two connections or terminals α and ζ and the projection images, for example. v={p 1 , . . . , p NK, α, ζ }. The set of edges E is formed by addition of edges of the source or the start node point α to the images of the first projection view V 1 . An edge is then added for each image of the kth projection view v k  to all images of the k+1th projection view v k+1 . The images of the last projection view are connected to the end node point ζ. The directed edges are weighted by an image dimension d for each of the two projection images and if one of the node points is not a projection image (a terminal α or ζ), by a constant of c=1. 
       FIG. 3  shows the result of the projection graph for a very small artificial scan. The projection images along each path which connects the two terminals α and ζ is a possible gating. The shortest path between them minimizes the total of the distances between adjacent projection directions. An efficient algorithm for the shortest path problem in a circuit-free directed graph with non-negative edge weightings is known from E. W. Dijkstra, “A Note on Two Problems in Connexion with Graphs” in Numeric Mathematics 1, pages 269 to 271. This algorithm produces the dummy code of a change which contains simple subpath conditions, as will be described below. 
     For optimum efficiency of the projection graph a few other items of information known in advance are also considered. At first the angle increase of consecutive angulations should be small; otherwise the sinogram movement dominates and the heart phase change becomes negligible. Furthermore data inconsistencies of consecutive C-arm-passes can additionally disturb the already described relationship and dominate the changes in the image content. Further factors to be considered are noise, the dynamics of the contrast medium and non-heart movements. This will be taken into account by the preprocessing and by the introduction of gating restrictions described below. 
     In accordance with the previous paragraphs the projection data is to undergo preprocessing. In such cases the following processing steps in accordance with  FIG. 6  can be performed for a projection image: 
     S 1  Preprocessing of 3D Reconstruction Algorithms 
     
         
         
           
             Carrying out preprocessing of 3D reconstruction algorithms and selection of the images which make a direct contribution to the computation of the 3D volume. This preprocessing can generally include, but is not restricted to the correction algorithms for scattered radiation, beam hardening, truncation, overradiation, low frequency drop and ring artifacts, as is described for example in Zellerhoff Et al. in “Low contrast 3D reconstruction from C-arm data”, Proceedings of SPIE, Medical Imaging  2005 , Vol. 5745, pages 646 to 655, or US 2006/0120507 A1.
 
S 2  Reduction of the Image Data
 
             The computation can be speeded up in this way.
 
S 3  Filtering
 
             Because of the detector rotation between adjacent angle positions common structures, such as edges for example, do not overlap exactly. To compensate for this influence lowpass filtering, for example a Gauss filter kernel, is applied.
 
S 4  Computing the Size of the Image Gradient (Optional)
 
             The image gradient supplies structural information about the heart geometry.
 
S 5  Forming a Region of Interest (ROI)
 
             The sinogram movements extend over the complete projection image. To reduce this influence the projection images are truncated to a region of interest (ROI) required by the user so that they contain the complete heart in all projection images and heart phases. 
           
         
       
    
     In general any grayscale measured values can be used as distance measured value d in the image-based gating algorithm. In the present case for example three different distance measurements, the Euclidean distance, the correlation coefficient and an SVD-based measurement, which is described in A. Shnayderman, A. Gusev, and A. Eskicioglu, “An svd-based grayscale Image quality measure for local and global assessment,” IEEE Transactions on Image Processing 15, pages 422 to 429, February 2006, are used. The Euclidean distance is viewed as especially advantageous because of safe and stable results with low computing effort. 
     To further improve the gating result, a regulation of the length of consecutive, selected projections from the same C-arm pass in a specific period is introduced. This period depends on the average heart rate which is also based on estimated image information provided. Therefore the option is introduced of performing a simple restricted, shortest-path search using the Dijkstra algorithm. In each step of the Dijkstra path search, for each possible subpath taking into account an additional validation value v, the current path outlay is added to. The algorithm produces the dummy code of the modified path search. The only change to the standard algorithm is in the line  17  and  18  of the appended program code, in which the validity value v is replaced by a function “Validity”. The validity value is zero for valid gatings and infinite for non-valid gatings. A path is valid if, within of a time frame of w, no more than m projection images of an individual pass were selected. This allows the selection of only possible solutions in respect of the characteristic of the heart cycle. It is known from “Cardiovascular Physiology Concepts” by Richard E. Klabunde, Lippincott Williams &amp; Wilkins, July 2004, (http://www.cvphysiology.com) that specific heart phases have a specific maximum period which is forced by the introduced validity value, i.e. cannot be exceeded. 
     Experience shows that the average heart rate Ĥ and the average time ΔT between two consecutively recorded projection images give a good intuition of how the validity parameters m and w can be parameterized. The average heart rate allows an upper limit for the diastolic or systolic period. The following heuristic values can be used for gating and have proved to be advantageous: 
     
       
         
           
             
               w 
               = 
               
                 0.65 
                 · 
                 
                   1 
                   
                     H 
                     ^ 
                   
                 
               
             
             , 
             
                 
             
             ⁢ 
             
               m 
               = 
               
                 w 
                 
                   Δ 
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   T 
                 
               
             
           
         
       
     
     This makes it possible for no more than 65% of the projections during a part of 65% of the time of a heart cycle to be selected from a single pass. The average heart rate is patient-specific and needs a derivation of the image data for a pure image-based algorithm. A method for determining the image-based mean heart rate will be described below. 
     During a forwards pass the C-arm rotates from an angle  1  to N and then pauses for a certain time. The backwards pass is then started and images are collected again, which are now recorded in the reverse order at the angles N to 1. The diagram in  FIG. 4  shows the EKG-measured heart phases, plotted over the acquisition time. At a constant heart rate two intersection points per heart cycle can typically be observed. Shown as a dotted line in  FIG. 5  is the normalized EKG distance between pairs of projection images for the same angulation. The distance for two projections P 1 , P 2  is produced by min cε{0,1,−1} |τ(p 1 )−τ(p 2 )+c|. The extended curve in  FIG. 5  shows the normalized image-based distance measurement value d for the same pair of projection images. It is clearly evident from this that the set of times in which the heart phase of a combination of forwards and backwards passes is the same corresponds to a minimum of the image-based distance function. The core idea of the present image-based algorithm for estimated average heart rate is to create an artificial heart signal which features the same set of intersection points. This algorithm operates as follows: 
     Let L in the following scenario be the number of the forwards and backwards combinations (F/B combinations) In a first phase of the algorithm the image-based distance curve is determined for each of the L F/B combinations. For each of the curves the set of the local minima R i  is detected. The set of all combinations            ={R 1 , . . . , R L }.
     In the second phase of the algorithm an artificial heart signal with an assumed constant heart rate h is created. Through this a graphical representation can be created for each F/B combination with the artificial heart signal, similar to that shown in  FIG. 4 . Next the minima A h ={A 1   h , . . . , A L   h } for each of the F/B combinations are computed by determination of the heart phase intersection points in the artificial signal. 
     For a quality measurement the match between             and each A h  is determined; a function λ M  (x) will be introduced, which for each set of the minima M of           or A h  creates a triangular form. It assumes the value one if x is a minimum, and the value zero if x lies in the middle between two consecutive minima and a linear interpolation value for intermediate values. Expressed in visual terms, this function is a triangle with the height 1, centered around each minimum value. Using λ M (x) we can define the following target function to be minimized:
               ∈     (   h   )       =       ∑     i   =   1     L     ⁢     ∫         (         λ     R   i       ⁡     (   x   )       -       λ     A   i   h       ⁡     (   x   )         )     2     ⁢     ⅆ   x                 
which measures the quadratic difference between the reference and the artificial triangle functions of the minima for all combinations of the forwards/backwards passes. ε is minimized by discretizing the search area [h min , h max ] and conducting a complete search. The optimum heart rate h will be interpreted as the average heart rate. In order to stabilize the estimated average heart rate a certain part of the best optimized heart rate is averaged. The estimated average heart rate can be further improved by an explicit change of the heart signal to minimizeε.
 
     In cardiac C-arm computer tomography a number of C-arm rotations are recorded in turn (DynaCT Cardiac ECG-gated protocol). The inventive method of selecting suitable heart phases with an image-oriented method achieves the result of enabling a suitable heart phase to be found for a gating even without recording an EKG. For N C-arm rotations N projection images are recorded for each projection angle. A gating is determined which minimizes the sum of the differences of the projection images from consecutive projection angles. As an ancillary condition the mean heart rate is computed in an image-oriented manner and accordingly a timely switch in the selection of the C-arm rotations is promoted. 
     The EKG-based selection method can lead to an incorrect selection of projection images. The relative heart phase primarily does not yet provide any information about the movement state of the heart. The phases of relative rest during given fixed heart rates are known from experience. In the clinical environment the heartbeat length varies widely however. Within 20s a patient heart rate of between 50 bpm and 120 bpm can be observed. The heart is described in a model manner so that the systole occurs in a relatively constant predetermined absolute time. The variance in the heart rate is largely brought about by a lengthening or shortening of the diastolic phase. Thus the same relative heart phases are shown the same states of the heart. 
     A model-based access would have the disadvantage of not taking account of patient-dependent variations. An image-based selection variant is independent of basic assumptions. It searches out on the basis of existing projection recordings the phases of relative heart rest. 
     The image-based selection of the heart phases in the cardiac 3D imaging from projection images, enables 3D images of heart phases to be obtained even retrospectively without executing an EKG with less movement and thus with less unsharpness. 
     The typical algorithm, which determines the shortest path in the projection graphs, described in E. W. Dijkstra, “A Note on Two Problems in Connexion with Graphs” in Numerische Mathematik 1, pages 269 to 271 is reproduced in modified form G=(V, E) below. The function “getpath” generates the shortest path by means of iteration by mapping the predecessor P. The function “validity” produces the validity value for a subpath (subpath). 
     
       
         
               
             
               
               
             
               
               
             
               
               
             
               
             
               
               
             
               
             
               
               
             
               
             
               
               
             
           
               
                   
               
             
             
               
                  1: P ← ∅ // Determine the predecessor of each node point which is to be 
               
               
                 reached on the shortest path to this node point. 
               
             
          
           
               
                  2: D s (s) ← 0 
                 // Determine the effort for reaching a node 
               
             
          
           
               
                   
                 point from the source. 
               
             
          
           
               
                  3: Q ← V 
                 // Set of node points to be checked 
               
             
          
           
               
                  4: for all u ε V to which u ≠ s applies do 
               
             
          
           
               
                  5: 
                 D s (u) ← +∞ 
               
             
          
           
               
                  6: End for 
               
               
                  7: while Q ≠ ∅ ; do 
               
             
          
           
               
                  8: 
                 find u ε Q such that D s (u) = min u′εQ (D s (u′)) 
               
               
                  9: 
                 Q ← Q | u 
               
               
                 10: 
                 for all neighbors v ε Q of u do 
               
               
                 11: 
                 if u = s or v = t then 
               
               
                 12: 
                 a ← 1 
               
               
                 13: 
                 else 
               
               
                 14: 
                 a ← d(u, v) 
               
               
                 15: 
                 end if 
               
               
                 16: 
                 subpath = getpath(p, u) ∪ v 
               
               
                 17: 
                 if D s (u) + a + validity(subpath) &lt; D s (v) then 
               
               
                 18: 
                 D s (v) ← D s (u) + a + validity(subpath) 
               
               
                 19: 
                 P(u) = v 
               
               
                 20: 
                 end if 
               
               
                 21: 
                 end for 
               
             
          
           
               
                 22: end while 
               
             
          
           
               
                 23: return 
                 getpath(P; t)