trouble starting saturn

I have a 1997 Saturn 4door sedan. This morning it started weird..turned the key & nothing happened, turned again & it started. Next went to pick up a few things & when I tried to start it again..nothing. . No clicks, no cranking. Tried for a few minutes..nothing. Went into another store & 20 minutes later tried to start again..started right up. I went to Autozone & they tested the battery & said it was bad. But this makes no sense to me because it started without a jump. I don't know if it's related, but I've also noticed the dashboard lights flicker when I'm driving. They have done this for a long time. Thanks for your help.