Leksell Gamma Knife is a mini-invasive technique to obtain a complete destruction of cerebral lesions delivering a single high dose radiation beam. Positron Emission Tomography (PET) imaging is increasingly utilized for radiation treatment planning. Nevertheless, lesion volume delineation in PET datasets is challenging because of the low spatial resolution and high noise level of PET images. Nowadays, the biological target volume (BTV) is manually contoured on PET studies. This procedure is time expensive and operator-dependent. In this article, a fully automatic algorithm for the BTV delineation based on random walks (RW) on graphs is proposed. The results are compared with the outcomes of the original RW method, 40% thresholding method, region growing method, and fuzzy c-means clustering method. To validate the effectiveness of the proposed approach in a clinical environment, BTV segmentation on 18 patients with cerebral metastases is performed. Experimental results show that the segmentation algorithm is accurate and has real-time performance satisfying the physician requirements in a radiotherapy environment.