Method Dijkstra

graph_implement.cpp:337–383

}

void ALGraph::Dijkstra(int strtID){
    //Clear previous result
    ClearVisit();
    ResetDistance();
    //Set start vex info to all vertexes
    for(int i = 0; i < vexList.size(); i++)
        vexList[i].info->strtVexInfo = vexList[strtID].info;
    //Start dijkstra
    vexList[strtID].info->distance = 0;
    vexList[strtID].access("strt");
    while(true){
        //Find next
        int minVexID = -1;
        for(int i = 0; i < vexList.size(); i++){
            if(vexList[i].visited || vexList[i].info->distance == VexInfo::INF)
                continue;
            if(minVexID == -1)
                minVexID = i;
            else if(vexList[i].info->distance < vexList[minVexID].info->distance)
                minVexID = i;
        }
        if(minVexID == -1)
            break;
        //Set visit to edge and vex
        ALArc *edge = FindArc(vexList[minVexID].info->preVexID, minVexID);
        if(edge){
            if(type == UDG && GetIdOf(edge->gArc->edVex()) != minVexID)
                edge->gArc->reverseDirection();
            edge->visit();
        }
        vexList[minVexID].visit();
        //Find adjacent
        for(ALArc *p = vexList[minVexID].firstArc; p != nullptr; p = p->nextArc){
            if(!vexList[p->eVexID].visited){
                if(GetIdOf(p->gArc->edVex()) != p->eVexID)
                    p->gArc->reverseDirection();
                p->access();
                if(vexList[p->eVexID].info->distance == VexInfo::INF ||
                        vexList[p->eVexID].info->distance > vexList[minVexID].info->distance + p->weight){
                    vexList[p->eVexID].info->preVexID = minVexID;
                    vexList[p->eVexID].info->distance = vexList[minVexID].info->distance + p->weight;
                    vexList[p->eVexID].access(QString::asprintf("%d", vexList[p->eVexID].info->distance));
                }
            }
        }
    }
}

AMLGraph* ALGraph::ConvertToAML(){
    AMLGraph *converted = new AMLGraph(type);