According to scriptures Lord Shiva worships Krishna, Krishna Worships Lord Shiva and Parvati, Goddess Parvati Worships Krishna, Vishnu Ji worships Shiv ji, Shiv ji worships Vishnu Ji . Why are they worshipping each other?
Krishna described the powers of Shiva.
The holy one said, "Verily, Drona's son had sought the aid of that highest of all the gods, the eternal Mahadeva. It was for this that he succeeded in slaying, single-handed, so large a number of warriors. If Mahadeva be gratified, he can bestow even immortality. Girisha can give such valour as will succeed in checking Indra himself. I know Mahadeva truly, O bull of Bharata's race! I know also his various acts of old. He, O Bharata, is the beginning, the middle, and the end of all creatures. This entire universe acts and moves through his energy.
That is the reason why Krishna did penance to Shiva despite being avatar of Vishnu to obtain his son Pradyumna.
That son whom I obtained through ascetic penances and observances of austere brahmacarya for twelve years on the breast of Himavati whither I had gone for the purpose, that son of mine, Pradyumna, of great energy and a portion of Sanat-kumara himself, begotten by me upon my wife Rukmini who had practised vows as austere as mine, that hero even never solicited this best of objects, this unrivalled discus, which thou of little understanding had solicited!
Arjuna described Krishna which can be the reason why people and other gods worship him.
Arjuna said, "It is meet, Hrishikesa, that the universe is delighted and charmed in uttering thy praise, and the Rakshasas flee in fear in all directions, and the hosts of the Siddhas bow down (to thee). And why should they not bow down to thee, O Supreme Soul, that are greater than even Brahman (himself), and the primal cause? O thou that art Infinite. O God of the gods, O thou that art the refuge of the universe, thou art indestructible, thou art that which is, and that which is not and that which is beyond (both). Thou art the First God, the ancient (male) Being, thou art the Supreme refuge of this universe. Thou art the Knower, thou art the Object to be known, thou art the highest abode.
By thee is pervaded this universe, O thou of infinite form. Thou art Vayu, Yama, Agni, Varuna, Moon, Prajapati, and Grandsire.