Date：2019-06-18 14:14:31
单源最短路径
Dijskra算法
伪码描述
1 //G为图，全局变量；数组d为源点到达各个点的最短路径长度；s为初始顶点 2 Dijskra (G, d[], s) 3 { 4 初始化; 5 for(i<=n) 6 { 7 u = 使d[u]最小的还未被访问的定点的编号 8 vis[u] = 1; 9 for(从u出发能到达的所有顶点v)10 {11 if(vis[v]==0 && 以u为中介点使得s到v的距离比d[v]更近)12 优化d[v];13 令v的前驱pre[v]=u来记录最短路径14 }15 }16 } 邻接矩阵实现
1 const int M = 1e3, INF=1x3fffffff; 2 int n, grap[M][M], vis[M]={ 0}, d[M]; 3 4 void Dijskra(int s) //s为起点 5 { 6 fill(d, d+M, INF); //数组整体赋值 7 fill(vis, vis+M, 0); 8 d[s] = 0; //s到自身为0 9 for(int i=1; i<=n; i++)10 {11 int u=0, Min=INF;12 for(int j=1; j<=n; j++) //寻找未访问的结点中最小的结点u13 if(vis[j]==0 && d[j] 邻接表实现
1 struct node 2 { 3 int v, w; 4 }; 5 6 vector adj[M]; 7 int d[M], vis[M], n; 8 9 void Dijskra(int s)10 {11 fill(d, d+M, INF);12 fill(vis,vis+M,0);13 d[s] = 0;14 for(int i=1; i<=n; i++)15 {16 int u=0, Min=INF;17 for(int j=1; j<=n; j++)18 if(vis[j]==0 && d[j] 多条最短路径求解第二尺度最优路径
1 //Q1: 求代价最小的最短路径 2 int cost[M][M]; //cost[u][v]表示u到v的代价 3 int c[M] //c[u]表示s到u的最少代价 4 5 fill(c,c+M,INF); 6 c[s]=0; 7 for(int v=1; v<=n; v++) 8 { 9 if(vis[v]==0 && grap[u][v]!=INF)10 {11 if(d[u]+grap[u][v] w[v])37 w[v] = w[u] + weight[v];38 }39 }40 41 //Q3：求最短路径的条数42 int num[M];43 44 fill(num, num+M, 0);45 num[s] = 1;46 for(int v=1; v<=n; v++)47 {48 if(d[u]+grap[u][v] < d[v])49 {50 d[v] = d[u] + grap[u][v];51 num[v] = num[u];52 }53 else if(d[u]+grap[u][v]==d[v])54 num[v] += num[u];55 } 算法实现
1 /* 2 Sample Input: 3 //v, e, s 4 6 8 0 5 0 1 1 6 0 3 4 7 0 4 4 8 1 3 2 9 2 5 110 3 2 211 3 4 312 4 5 313 Sample Output:14 0 1 5 3 4 615 */16 17 #include 18 #include 19 using namespace std;20 const int M=1e3, INF=1e9;21 int n,m,s,grap[M][M],vis[M],d[M],path[M];22 23 void Dijskra(int s)24 {25 fill(d, d+M, INF);26 fill(vis,vis+M,0);27 for(int i=0; i
Dijskra算法+DFS
1 //Dijskra：记录所有的最短路径 2 vector pre[M]; 3 4 void Dijskra(int s) 5 { 6 fill(d,d+M,INF); 7 d[s] = 0; 8 for(int i=0; i pre, optPath, tempPath; //path为逆序,即v->s39 40 void DFS(int v)41 {42 if(v == s) //s为pre递归树的叶子结点，也即图的起点43 {44 tempPath.push_back(s);45 46 int value=0;47 //计算边权之和48 for(int i=tempPath.size()-1; i>0; i--)49 {50 int id = tempPath[i]; idNext=tempPath[i-1];51 value += v[id][idNext];52 }53 //计算点权之和54 for(int i=tempPath.size()-1; i>=0; i--)55 {56 int id = tempPath[i];57 value += w[id];58 }59 //计算路径条数60 cnt++;61 62 //选择最优路径63 if(value > optValue)64 {65 optValue = value;66 optPath = tempPath;67 }68 tempPath.pop_back();69 return ;70 }71 72 tempPath.push_back(v);73 for(int i=0; i
1 //邻接表法 2 int n,d[M],w[M][M]; 3 vector grap[M]; 4 5 //判断有无负环并且给出最短路径 6 bool Bellman(int s) 7 { 8 fill(d,d+M,INF); 9 d[s] = 0;10 for(int i=0; i 1 /* 2 Sample Input: 3 5 6 0 2 4 1 2 1 5 3 5 0 1 1 6 0 2 2 7 0 3 1 8 1 2 1 9 2 4 110 3 4 111 Sample Output:12 2 413 */14 15 #include 16 #include 17 #include 18 #include 19 #include 20 using namespace std;21 const int M=1e3,INF=1e9;22 struct node23 {24 int v, dis;25 node(int _v, int _dis) : v(_v), dis(_dis) {}26 };27 vector adj[M];28 int n,weight[M];29 int d[M],w[M],t[M];30 set pre[M];31 32 void Bellman(int s)33 {34 fill(d, d+M, INF);35 fill(t, t+M, 0);36 fill(w, w+M, 0);37 d[s] = 0;38 w[s] = weight[s];39 t[s] = 1;40 for(int i=0; i w[v])61 w[v] = w[u] + weight[v];62 pre[v].insert(u); //BF算法会多次访问同一个结点，使用set可以去重63 t[v]=0;64 set ::iterator it;65 for(it=pre[v].begin(); it!=pre[v].end(); it++)66 t[v] += t[*it]; //重新计算最短路径条数67 }68 }69 }70 if(isLoose)71 break; //不再松弛时退出72 }73 }74 75 int main()76 {77 #ifdef ONLINE78 #else79 freopen("Test.txt", "r", stdin);80 #endif // ONLINE81 82 int m,s,v;83 scanf("%d%d%d%d", &n,&m,&s,&v);84 for(int i=0; i
1 /* 2 6 8 3 0 1 1 4 0 3 4 5 0 4 4 6 1 3 2 7 2 5 1 8 3 2 2 9 3 4 310 4 5 311 */12 #include 13 #include 14 using namespace std;15 const int M=220,INF=1e9;16 int n,m,dis[M][M];17 18 void Floyd()19 {20 for(int k=0; k