DirectedWeightedGraph

发表于 | 分类于

DirectedWeightedGraph

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
//
// Created by mfzhu on 2017/4/19.
//
#ifndef ALGORITHM_DIJKSTRA_H
#define ALGORITHM_DIJKSTRA_H
#include <iostream>
#include <vector>
#include <map>
using namespace std;
class Edge;
class directedGraphNode{
public:
    int label;
    vector<Edge*> neighbors;
    directedGraphNode(int l): label(l) {};
};
class Edge{
public:
    int weight;
    directedGraphNode* start;
    directedGraphNode* end;
    Edge(directedGraphNode* s, directedGraphNode* e, int w): weight(w), start(s), end(e){};
};
class directedWeightedGraph{
public:
    directedWeightedGraph();
    ~directedWeightedGraph(){};
//    void dfs();
//    void bfs();
//    void prime();
//    void kruskal();
    void dijkstra(int start);
//    void Bellman_Ford();
    void insertEdge(int start, int end, int weight);
    void insertNode(int val);
    void print();
private:
    int nNode;
    int nEdge;
    map<int, directedGraphNode*> nodeTable;
    void insertNode(map<int, directedGraphNode*> &nodeTable, int val);
    void insertEdge(map<int, directedGraphNode*> &nodeTable, int start, int end, int val);
    void dijkstra(map<int, directedGraphNode*> nodeTable, int start);
};
directedWeightedGraph::directedWeightedGraph() {
    cout << "please input the number of vertex:" << endl;
    cin >> nNode;
    cout << "please input the number of edge:" << endl;
    cin >> nEdge;
    for (int i = 0; i < nNode; i++){
        cout << "please input the label of vertex:" << endl;
        int label;
        cin >> label;
        directedGraphNode* node = new directedGraphNode(label);
        nodeTable.insert({label, node});
    }
    for (int i = 0; i < nEdge; i++){
        cout << "please input the info of Edge:" << endl;
        int start;
        int end;
        int weight;
        cin >> start >> end >> weight;
        Edge* edge = new Edge(nodeTable[start], nodeTable[end], weight);
        nodeTable[start]->neighbors.push_back(edge);
    }
}
void directedWeightedGraph::print() {
    auto it = nodeTable.begin();
    while(it != nodeTable.end()){
        cout << "the node label is :" << it->first << endl;
        cout << "the node info is:" << endl;
        for (auto i : it->second->neighbors){
            cout << i->start->label << "->" << i->end->label << "  weight:" << i->weight << endl;
        }
        it++;
    }
}
void directedWeightedGraph::insertNode(map<int, directedGraphNode *> &nodeTable, int val) {
    if (nodeTable.find(val) == nodeTable.end()){
        directedGraphNode* node = new directedGraphNode(val);
        nodeTable.insert({val, node});
    }else{
        cout << "the node is existed" << endl;
    }
}
void directedWeightedGraph::insertNode(int node) {
    insertNode(nodeTable, node);
}
void directedWeightedGraph::insertEdge(map<int, directedGraphNode *> &nodeTable, int start, int end, int w) {
    Edge* e = new Edge(nodeTable[start], nodeTable[end], w);
    nodeTable[start]->neighbors.push_back(e);
}
void directedWeightedGraph::insertEdge(int start, int end, int weight) {
    insertEdge(nodeTable, start, end, weight);
}
void directedWeightedGraph::dijkstra(map<int, directedGraphNode *> nodeTable, int start) {
    map<int, int> visited{{start, 0}};
    map<int, int> unvisted;
    for (auto i : nodeTable){
        if (i.first != start) unvisted.insert({i.first, INT8_MAX});
    }
    for(auto i: nodeTable[start]->neighbors){
        unvisted[i->end->label] = i->weight;
    }
    while(!unvisted.empty()){
        int cur_min_label = unvisted.begin()->first;
        int cur_min_weight = unvisted.begin()->second;
        for (auto it = unvisted.begin(); it != unvisted.end(); it++){
            if (it->second < cur_min_weight){
                cur_min_label = it->first;
                cur_min_weight = it->second;
            }
        }
        visited.insert({cur_min_label, cur_min_weight});
        unvisted.erase(cur_min_label);
        for (auto it = unvisted.begin(); it != unvisted.end(); it++){
            int cur_distance = it->second;
            for (auto edge: nodeTable[it->first]->neighbors){
                if (edge->end->label == cur_min_label && (edge->weight + cur_min_weight) < cur_distance){
                    it->second = edge->weight + cur_min_weight;
                }
            }
        }
    }
    for(auto it = visited.begin(); it != visited.end(); it++){
        cout << start << " " << it->first << ":" << it->second << endl;
    }
}
void directedWeightedGraph::dijkstra(int start) {
    dijkstra(nodeTable, start);
}
#endif //ALGORITHM_DIJKSTRA_H