In the early middle ages (and beyond, in the case of rather sparsely populated lands like Scotland) there were very few "capitals" in the traditional sense. The "capital" was where the king was, and kings spent a lot of time on the road and on campaign. You might be best served looking for biographies of kings in the relevant period, trying to figure out what places they especially favored.