"Shall we run next week?"
It is more or less at the end. The last word (as we think of word divisions) is the question particle, "ka." The word before that is "hashirimashoo," which is the verb to run, "hashiru," in a sort of polite optative mood, so without the "ka," the sentence would be "Let's run next week."
One context that you would use ましょうか exclusively is when offering to help someone (offering to do something that will benefit them). Otherwise, they're both used to extend invitations.
ませんか feels slightly more polite to me. When you say ましょうか you're already assuming that the person will agree, while if you use ませんか you're giving the person an out to say "no".
Nihongo no Sato has a good article in Japanese.