多段圖的最短路徑問題

建立一個從源點S到終點T的多段圖浮毯，設計一個動態(tài)規(guī)劃算法求出從S到T的最短路徑值，并輸出相應的最短路徑泰鸡。

例圖

改為序號下標

思路

動態(tài)規(guī)劃

首先確定能分段债蓝，即每一層的各個結點互不連通，后驅結點均在同一層盛龄。
通過有一定修改的bfs進行分段饰迹，然后從最后一段，依段數(shù)逐段取最小路徑余舶，有點類似最小路徑算法啊鸭。

#include <iostream>
#include <vector>
#include <deque>
#define NODE_COUNT 8
#define MAX_SEG 5
#define INF 255
#define NO_NEXT -1
using namespace std;

int nodes[NODE_COUNT][NODE_COUNT];
int beginPos;
int endPos;

struct Segment {
    vector<int> nodes;
};

void setEdge(int graph[NODE_COUNT][NODE_COUNT], int from, int to, int weight) {
    graph[from][to] = weight;
}

bool isConnect(int graph[NODE_COUNT][NODE_COUNT], int from, int to) {
    return graph[from][to] != INF;
}

int getWeight(int graph[NODE_COUNT][NODE_COUNT], int from, int to) {
    return graph[from][to];
}

void setSegment(int graph[NODE_COUNT][NODE_COUNT], vector<Segment>& segments,int beginPos,int endPos) {
    int pos = beginPos;
    //避免同一段中結點被重復push
    bool check[NODE_COUNT] = {false};
    //bfs隊列
    deque<int> nowSegNodes;
    nowSegNodes.push_back(beginPos);
    deque<int> nextSegNodes;
    //第一段只有beginPos
    Segment newSeg;
    segments.push_back(newSeg);
    segments[0].nodes.push_back(pos);
    int segIndex = 1;
    while (pos != endPos) {
        //cout << "現(xiàn)在在bfs" << pos << "結點" << endl;
        for (int i = 0; i < NODE_COUNT; i++) {
            if (!check[i] && isConnect(graph, pos, i)) {
                if (segments.size() - 1 < segIndex) {
                    Segment newSeg;
                    segments.push_back(newSeg); 
                }
                //分段
                //cout << i << "是第" << segIndex << "段" << endl;
                segments[segIndex].nodes.push_back(i);
                //入下一段的隊
                nextSegNodes.push_back(i);
                check[i] = true;
            }
        }
        //出隊
        nowSegNodes.pop_front();
        //如果當前段的隊列沒有結點了
        if (nowSegNodes.empty()) {
            //下一段的隊列置空，成為該段隊列
            nowSegNodes.swap(nextSegNodes);
            segIndex++;
        }
        pos = nowSegNodes.at(0);
    }
}

void findMinRoute(int graph[NODE_COUNT][NODE_COUNT], vector<Segment>& segments, int beginPos, int endPos) {
    int segCount = segments.size();
    //記錄距離endPos最近的鄰接的node
    int nextPos[NODE_COUNT];
    //記錄該pos到endPost的距離
    int dist[NODE_COUNT];
    dist[endPos] = 0;
    nextPos[endPos] = NO_NEXT;
    //遍歷每個分段
    for (int nowSeg = segCount - 2; nowSeg >= 0; nowSeg--) {
        //遍歷分段中每個pos
        //cout << "分段" << nowSeg << "開始遍歷" << endl;
        for (int nowNodeIndex = 0; nowNodeIndex < segments[nowSeg].nodes.size(); nowNodeIndex++) {
            int nowPos = segments[nowSeg].nodes[nowNodeIndex];
            //cout << nowPos << endl;
            //int minDist = INF;
            dist[nowPos] = INF;
            //跟上個分段的Node作比較
            for (int lastSegNodeIndex = 0; lastSegNodeIndex < segments[nowSeg + 1].nodes.size(); lastSegNodeIndex++) {
                int lastSegNodePos = segments[nowSeg + 1].nodes[lastSegNodeIndex];
                if (isConnect(graph, nowPos, lastSegNodePos) && getWeight(graph, nowPos, lastSegNodePos) + dist[lastSegNodePos] < dist[nowPos]) {
                    dist[nowPos] = getWeight(graph, nowPos, lastSegNodePos) + dist[lastSegNodePos];
                    nextPos[nowPos] = lastSegNodePos;
                }
            }
        }
        //cout << "分段" << nowSeg << "遍歷完成" << endl;
    }
    cout << "最短路徑:";
    int tempindex = beginPos;
    cout << beginPos;
    while (tempindex != endPos) {
        cout << "-->" << nextPos[tempindex];
        tempindex = nextPos[tempindex];
    }
    cout << "\n";
    cout << "最短路徑長度:" << dist[beginPos] << endl;
}

int main(void) {
    vector<Segment> segments;
    beginPos = 0;
    endPos = 7;

    for (int i = 0; i < NODE_COUNT; i++)
        for (int j = 0; j < NODE_COUNT; j++)
            nodes[i][j] = INF;

    //初始化
    setEdge(nodes, 0, 1, 1);
    setEdge(nodes, 0, 2, 2);
    setEdge(nodes, 0, 3, 5);
    setEdge(nodes, 1, 4, 4);
    setEdge(nodes, 1, 5, 11);
    setEdge(nodes, 2, 5, 5);
    setEdge(nodes, 2, 4, 9);
    setEdge(nodes, 2, 6, 16);
    setEdge(nodes, 3, 6, 2);
    setEdge(nodes, 4, 7, 18);
    setEdge(nodes, 5, 7, 13);
    setEdge(nodes, 6, 7, 2);

    //分段
    setSegment(nodes, segments, beginPos, endPos);

    int segCount = segments.size();
    for (int i = 0; i < segCount; i++) {
        cout << "第" << i << "段:";
        for (int j = 0; j < segments[i].nodes.size(); j++) {
            cout << segments[i].nodes[j] << " ";
        }
        cout << "\n";
    }

    findMinRoute(nodes, segments, beginPos, endPos);
    system("pause");
    return 0;
}

運行示例

有向無環(huán)圖的最短路徑問題

建立一個從源點S到終點E的有向無環(huán)圖匿值，設計一個動態(tài)規(guī)劃算法求出從S到E的最短路徑值赠制，并輸出相應的最短路徑。

示例

改為序號下標

思路

動態(tài)規(guī)劃

拓撲排序后千扔，由后至前動態(tài)規(guī)劃憎妙。
實現(xiàn)上用鄰接矩陣檢索效率更高一些，這里用鄰接表是寫拓撲排序比較方便曲楚。
結構體數(shù)組組厘唾、vector一起用，并且元素都是int的時候很容易寫錯龙誊，需要多注意一點抚垃。

#include <iostream>
#include <vector>
#include <deque>
#define NODE_COUNT 6
#define INF 255
using namespace std;

struct Node {
    int pos;
    int weight;
};

vector<Node> graph[NODE_COUNT];

int indegree[NODE_COUNT] = {0};
int beginPos;
int endPos;

void setEdge(vector<Node> graph[NODE_COUNT],int from, int to, int weight, int indegree[NODE_COUNT]) {
    //鄰接表
    Node node;
    node.pos = to;
    node.weight = weight;
    graph[from].push_back(node);
    indegree[to]++;
}

void topoSort(vector<Node> graph[NODE_COUNT], int indegree[NODE_COUNT], vector<int>& linearList) {
    deque<int> queue;
    for (int i = 0; i < NODE_COUNT; i++) {
        if (indegree[i] == 0) {
            queue.push_back(i);
        }
    }
    while (!queue.empty()) {
        int pos = queue.front();
        queue.pop_front();
        linearList.push_back(pos);
        for (int j = 0; j < graph[pos].size(); j++) {
            if (!--indegree[graph[pos].at(j).pos]) {
                queue.push_back(graph[pos].at(j).pos);
            }
        }
    }
}

int getWeight(vector<Node> graph[NODE_COUNT],int from,int to) {
    for (int i = 0; i < graph[from].size(); i++) {
        if (graph[from][i].pos == to) {
            return graph[from][i].weight;
        }
    }
    return INF;

}

void findMinRoute(vector<Node> graph[NODE_COUNT], int beginPos, int endPos,vector<int> linearlist) {
    int nextPos[NODE_COUNT];
    int dist[NODE_COUNT];
    for (int i = 0; i < NODE_COUNT; i++) {
        dist[i] = getWeight(graph, i, endPos);
    }
    dist[endPos] = 0;
    for (int i = NODE_COUNT - 2; i >= 0; i--) {
        int nowpos = linearlist[i];
        for (int j = 0; j < graph[nowpos].size(); j++) {
            if (graph[nowpos][j].weight + dist[graph[nowpos][j].pos] <= dist[nowpos]) {             
                nextPos[nowpos] = graph[nowpos][j].pos;
                dist[nowpos] = graph[nowpos][j].weight + dist[graph[nowpos][j].pos];

            }
        }
    }
    cout << "最短路徑長為:" << dist[beginPos] << endl;
    cout << "最短路徑為:";
    int temp = beginPos;
    cout << beginPos;
    while (temp != endPos) {
        cout << "-->" << nextPos[temp];
        temp = nextPos[temp];
    }
    cout << "\n";
}

int main(void) {

    beginPos = 0;
    endPos = 5;

    setEdge(graph, 0, 1, 1, indegree);
    setEdge(graph, 0, 2, 2, indegree);
    setEdge(graph, 1, 3, 6, indegree);
    setEdge(graph, 2, 1, 4, indegree);
    setEdge(graph, 2, 4, 3, indegree);
    setEdge(graph, 3, 4, 1, indegree);
    setEdge(graph, 3, 5, 2, indegree);
    setEdge(graph, 4, 5, 1, indegree);

    vector<int> list;
    topoSort(graph, indegree, list);
    cout << "拓撲排序:";
    for (int i = 0; i < list.size(); i++) {
        cout << list[i] << " ";
    }
    cout << "\n";

    findMinRoute(graph, beginPos, endPos, list);
    system("pause");
    return 0;
}

運行示例

最長遞增子序列問題

給定一個整數(shù)數(shù)組，設計一個動態(tài)規(guī)劃算法求出該數(shù)組中的最長遞增子序列趟大。

思路

動態(tài)規(guī)劃

從第一個元素開始鹤树，每個元素都遍歷k-1個之前的元素，記錄該元素及之前最大子序列長度逊朽。同時再用一個數(shù)組記錄前驅元素的下標罕伯。

#include <iostream>
#define LENGTH 10
#define NO_PRE -1
using namespace std;
int INDEX[LENGTH] = { 1,5,2,3,4,8,3,9,10,7 };

void printSeq(int* posRecord,int* index,int now) {
    if (posRecord[now] == NO_PRE) {
        cout << index[now] << " ";
        return;
    }
    printSeq(posRecord, index, posRecord[now]);
    cout << index[now] << " ";
}

void lis(int* index,int length) {
    int* lenRecord = new int[length];
    //記錄index中該位置元素的前一個元素
    int* posRecord = new int[length];
    lenRecord[0] = 1;
    for (int i = 0; i < length; i++){
        lenRecord[i] = 1;
        posRecord[i] = NO_PRE;
        for (int j = 0; j < i; j++) {
            if (index[j]<index[i] && lenRecord[j]>lenRecord[i] - 1) {
                lenRecord[i] = lenRecord[j] + 1;
                posRecord[i] = j;
            }
        }
    }
    //找出最長的length
    int maxLen = 0;
    int maxLenPos = 0;
    for (int i = 0; i < length; i++) {
        if (lenRecord[i] > maxLen) {
            maxLen = lenRecord[i];
            maxLenPos = i;
        }
    }
    //輸出子序列
    printSeq(posRecord, index, maxLenPos);
}



int main(void) {
    cout << "原序列:";
    for (int i = 0; i < LENGTH; i++) {
        cout << INDEX[i] << " ";
    }
    cout << "\n最大子序列:";
    lis(INDEX, LENGTH);
    cout << "\n";
    system("pause");
    return 0;
}

運行示例