对于有向图，要求必须经过图中某些点，找最短路径，构建模型分析？

问题：带权有向图（vertex号可能不连续），要求必须经过图中某些点，找出一个最短路径（非点的路径，给出了边的号和代价），，个人思路：使用邻接表以顶点为对象，但是，由于顶点号可能不是连续给出，读取一个边就要找对应的插入一条，这样建立比较麻烦，另外结果要给出路径边的号（这个可使用hash解决），使用十字链表，这个一样，就是容易获取出入度，结构复杂，最后还是需要hash 出路径边号、。。。最后一种思路，以边为对象，就是一条边一个起始点，终止点，代价；由于每个点的出度最大是8，边的数量比较巨大，不知道以边为对象建立结构和点为对象建立哪个更好，，，