This answer is somewhat taken fom a discussion with @alummat in the chat-room:
Worshiping anyone beside Allah is Shirk. But not everything is necessarily Shirk, even if it seems to you it is a kind of worshiping-a-being-other-than-Allah. The most famous example is the prostration of Angels for Adam, peace be upon him. The only one who refused to prostrate in that case was Satan and of course the only one who committed a sin in that case was again Satan. I know that the angels did prostrate for Adam was due to the direct command of Allah but I'm grabbing your attention to the fact that anyway it is possible that some prostrations done are not considered as Shirk. If there exists a possibility that prostration for someone is not Shirk then there would exist the possibility for many other things also not be Shirk, after all prostration is the highest state of worshiping according to Hadeeth and perhaps that's why a mosque is called Masjid (مسجد: place for Sojud or prostration).
You may then ask that the command for prostration was to the angels and not for the humans to prostrate for anyone else but let me then bring you some evidences from Qur'aan:
when Israelite are ordered to enter the city while prostrating:
وَإِذْ قُلْنَا ادْخُلُوا هَـٰذِهِ الْقَرْيَةَ فَكُلُوا مِنْهَا حَيْثُ
شِئْتُمْ رَغَدًا وَادْخُلُوا الْبَابَ سُجَّدًا وَقُولُوا حِطَّةٌ
نَّغْفِرْ لَكُمْ خَطَايَاكُمْ ۚ وَسَنَزِيدُ الْمُحْسِنِينَ
And when We said: Enter this city, then eat from it a plenteous (food)
wherever you wish, and enter the gate making obeisance, and say,
forgiveness. We will forgive you your wrongs and give more to those
who do good (to others). [2:58]
also [4:154] and [7:161]. According to Hadeeth on the gate of the city was written a text in the respect of which they were ordered to prostrate for entering the city
Another example is when Jacob --peace be upon him-- and his family, prostrating for Joseph --peace be upon him (recall the dream Joseph saw while he was a child: a sun and a moon and 11 stars falling in prostration for him, [12:4]):
وَرَفَعَ أَبَوَيْهِ عَلَى الْعَرْشِ وَخَرُّوا لَهُ سُجَّدًا ۖ وَقَالَ
يَا أَبَتِ هَـٰذَا تَأْوِيلُ رُؤْيَايَ مِن قَبْلُ قَدْ جَعَلَهَا
رَبِّي حَقًّا ۖ وَقَدْ أَحْسَنَ بِي إِذْ أَخْرَجَنِي مِنَ السِّجْنِ
وَجَاءَ بِكُم مِّنَ الْبَدْوِ مِن بَعْدِ أَن نَّزَغَ الشَّيْطَانُ
بَيْنِي وَبَيْنَ إِخْوَتِي ۚ إِنَّ رَبِّي لَطِيفٌ لِّمَا يَشَاءُ ۚ
إِنَّهُ هُوَ الْعَلِيمُ الْحَكِيمُ
And he raised his parents upon the throne and they fell down in
prostration before him, and he said: O my father! this is the
significance of my vision of old; my Lord has indeed made it to be
true; and He was indeed kind to me when He brought me forth from the
prison and brought you from the desert after the Shaitan had sown
dissensions between me and my brothers, surely my Lord is benignant to
whom He pleases; surely He is the Knowing, the Wise. [12:100]
Note that here Allah uses the phrase prostration for Yusuf as he says exactly the same about the angels: prostration for Adam, peace be upon them all: in Arabic compare له and لآدم .
But what do such verses really mean, worshiping someone else by the command of Allah? Allah Himself ordering for Shirk? Of course not! Neither Allah stated that to the angels nor Joseph ordered such to his father to fall in prostration for him, even though he was a prophet (and his father was a prophet too). The following is what the interpretation of the verse [12:100] brings on the desk, a Shia interpretation by Ahlul Bayt though:
source: البرهان في تفسير القرآن، ج3، ص: 205
ثم قال علي بن إبراهيم: و حدثني محمد بن عيسى، أن يحيى بن أكثم سأل موسى
بن محمد بن علي بن موسى مسائل، فعرضها على أبي الحسن (عليه السلام)، و
كان أحدها: أخبرني عن قول الله عز و جل: وَ رَفَعَ أَبَوَيْهِ عَلَى
الْعَرْشِ وَ خَرُّوا لَهُ سُجَّداً أسجد يعقوب و ولده ليوسف و هم
أنبياء؟ فأجاب أبو الحسن (عليه السلام): «أما سجود يعقوب و ولده ليوسف،
فإنه لم يكن ليوسف، و إنما كان ذلك من يعقوب و ولده طاعة لله، و تحية
ليوسف، كما كان السجود من الملائكة لادم و لك يكن لادم، و إنما كان ذلك
منهم طاعة لله و تحية لادم، فسجد يعقوب و ولده و سجد يوسف معهم شكرا لله
تعالى لاجتماع شملهم، ألم تر أنه يقول في شكره ذلك الوقت: رَبِّ قَدْ
آتَيْتَنِي مِنَ الْمُلْكِ وَ عَلَّمْتَنِي مِنْ تَأْوِيلِ الْأَحادِيثِ
فاطِرَ السَّماواتِ وَ الْأَرْضِ أَنْتَ وَلِيِّي فِي الدُّنْيا وَ
الْآخِرَةِ تَوَفَّنِي مُسْلِماً وَ أَلْحِقْنِي بِالصَّالِحِينَ.
Imam Redha --peace be upon him-- was asked about the verse [12:100]
around the case that Jacob --peace be upon him-- and his sons fell in
prostration for Joseph --peace be upon him-- while Jacob --peace be
upon him-- was himself a prophet? Imam Answered, the prostration of
Jacob and his sons for Joseph was not indeed for Joseph, but for
giving tribute to Joseph and obeying Allah. Like the prostration did
the angels for Adam and it was not indeed for Adam but for giving
tribute to Adam and obeying Allah. Thus, prostrated Jacob and his sons
and also prostrated Joseph together with them thanking Allah and it
was then that he said the context of the next verse [12:101]: "My
Lord! Thou hast given me of the kingdom and taught me of the
interpretation of sayings: Originator of the heavens and the earth!
Thou art my guardian in this world and the hereafter; make me die a
muslim and join me with the good."
So it is now clear that such prostration was indeed for respecting him but praying Allah, and of course Jacob --peace be upon him-- was not a Mushrik.
Now let me add one point, in one verse Allah stress that:
وَالنَّجْمُ وَالشَّجَرُ يَسْجُدَانِ
And the herbs and the trees do prostrate (to Him). [55:6]
This verse has an apparent meaning (Tafseer) and some hidden meanings (Ta'weel). You may like to think about the apparent meaning of the verse how herbs and the trees prostrate to Allah, do they bow or what? This can shift your understanding of deeds in Islam.
Actually even someone when greets another person from a far distance that the second person couldn't hear his voice, he may simply put his hand over his chest, recite the greeting slowly (enough to show he is saying something) and bend very slightly so that the second person understands he is saying a greeting to him. And who can ever claim this slight bending is praying someone beside Allah and thus Shirk? Another example is such a respecting tradition done at the beginning and ending of a fight in some martial arts. If it was the case that any bending was to be considered as Shirk a practicing Muslim should have been so careful all the times never to bend when something or someone is standing or sleeping or walking in front of him, tying his shoes or scraching his knees or picking up something mistakenly dropped on the ground from his hand and etc ... That way, the life would have been quite difficult and it is clear that Islam categorizes such a way of thinking as وسواس (Satanic inspirations from inside).
Therefore, all that I can say is that the intention is the ultimate point, judging and interpreting any deed highly depends on its background intention and it is backed by a famous Hadeeth from Imam Redha peace be upon him: الأعمال بالنیات.
Accusing the others for Shirk would of course be questioned in the Day and as Shirk is the biggest sin in Islam wrongly accusing someone for that would be the biggest wrong blame. Thus here I stress over the fact that Specifically Shia Muslims, who go to Ziyarah at the shrines, don't prostrate for Ahlul Bayt --peace be upon them-- or their descendants or other saints. We pray Allah near them but not toward them, rather only toward Qiblah (although an encouraged Salah need not be toward Qiblah, it can be done even while walking and etc, but anyway, certainly the graves are not Qiblah to those who are doing the Ziyarah). For your interest, we do not agree that prostration can be easily practiced by anyone in front of anyone. Indeed we do not do that at all but in front of Allah and while being at a Fardh prayer then also only toward Qiblah.
This answer encourages the questioner to ask the people who are doing such Ziyarah's, case by the case, about their intentions, before to judge them. And last but by no means least, note that all the Muslims pray toward a stone-made buiding named ka'bah and no one can raise the question if it is Shirk. Both worshiping and Shirk should be fully understood before judging the others if they are Mushrik or not.
PS. What follows are the points I can say about another answer given by brother @Suhaib:
Certainly your answer is not only based on Qur'aan! You have used many
Ahadeeth as well. Can you show me in the first verse you have quoted
the adverbs "just" and "directly"? / "O Hussien, Ask allah to forgive
our sins" is this Shirk really? We have the same saying about the holy
prophet in Qur'aan! And Hussain is a martyr and not a death, again
according to Qur'aan, peace be upon him. / In the 2nd verse you quoted
I grab your attention to من دونه whic means BESIDE Allah, and at least
no Shia considers the saints beside Allah but along with Him.
The pious people that you talk about are those whom practiced
worshiping idols for the first time, to be more precise, the pious
people died, the believers produced their sculptures to worship Allah
beside them, heir descendant thought their fathers were praying the
idols and worshiping the idols was originated. Of course we do not do
such, we still pray Allah like those believers at the same time that
we do not build any sculpture as well. Also in that verse you can
easily see Allah quote from them "نعبدهم" which means they were
worshiping the idols as gods beside the God, we are not similar
According to Qur'aan the believers were going to build a mosque over
the cave of the companions of the cave, and the non believers were
only leaving their cave on its own, only sealing them as for their
grave. And Allah never narrates a story for amusement, that has a
lesson inside it for me and you. Any Hadeeth that apparently
contradict the verses of Qur'aan is either fabricated or needs
interpretation, e.g. may be specified for some specific situation, and
for your interest Shia also has some similar Ahadeeth (like your last
quoted Hadeeth), but they never forbid Ziyarah in shrines! According
to Qur'aan specific times and positions can affect our mood of
worshiping Allah, like the middle of night and like the mosques. How
you can be sure the shrines are not other examples, like the houses
that Allah likes to His name be raised therein, according to Qur'aan