首页 > 代码库 > Dijksktra(测试源代码)
Dijksktra(测试源代码)
1、此程序为c++程序
2、以下代码可实现手动输入，即去掉代码中的/*...*/注释符，并同时去掉赋值代码段
3、源代码
#include<iostream>
using namespace std;
#define MaxInt 32767
#define MVNum 100
typedef struct
{
char vexs[MVNum];
int arcs[MVNum][MVNum], vexnum, arcnum;
}AMGraph;
int LocateVex(AMGraph G, char v);
void Create(AMGraph &G);
void ShortestPath_DIJ(AMGraph G, char vv0, char vv1);
int main()
{
AMGraph G;
char p = ‘y‘, v0 = ‘a‘, v1 = ‘f‘;
while (p == ‘y‘)
{
/*cout << "请输入起点和终点:";
cin >> v0 >> v1;*/
Create(G);
ShortestPath_DIJ(G, v0, v1);
cout << "再次执行请输入:y，不执行请输入:n" << endl;
cin >> p;
}
system("pause");
return 0;
}
//确定结点下标
int LocateVex(AMGraph G, char v)
{
int l, i;
for (l = 0, i = 0; i < G.arcnum; i++)
{
if (v == G.vexs[i])
{
l = i;
}
}
return l;
}
void Create(AMGraph &G)
{
int i, j, k, w;
char v1, v2;
/*cout << "请输入顶点数和边数:";
cin >> G.vexnum >> G.arcnum;
cout << "请输入顶点:";
for (i = 0; i < G.vexnum; i++)
{
cin >> G.vexs[i];
}*/
G.vexnum = 6;
G.arcnum = 8;
G.vexs[0] = ‘a‘;
G.vexs[1] = ‘b‘;
G.vexs[2] = ‘c‘;
G.vexs[3] = ‘d‘;
G.vexs[4] = ‘e‘;
G.vexs[5] = ‘f‘;
//初始化
for (i = 0; i < G.vexnum; i++)
{
for (j = 0; j < G.vexnum; j++)
{
G.arcs[i][j] = MaxInt;
}
}
/*for (k = 0; k < G.arcnum; k++)
{
cout << "请输入边的起点、终点及权值:";
cin >> v1 >> v2 >> w;
i = LocateVex(G, v1);
j = LocateVex(G, v2);
G.arcs[i][j] = w;
}*/
G.arcs[0][2] = 10;
G.arcs[0][4] = 30;
G.arcs[0][5] = 100;
G.arcs[1][2] = 5;
G.arcs[2][3] = 50;
G.arcs[3][5] = 10;
G.arcs[4][3] = 20;
G.arcs[4][5] = 60;
}
//最短路径
void ShortestPath_DIJ(AMGraph G, char vv0, char vv1)
{
int v0, v1, i, j, k, n, v, min, D[MVNum], Path[MVNum], S[MVNum];
char p[MVNum];
v0 = LocateVex(G, vv0);
v1 = LocateVex(G, vv1);
for (i = 0; i < G.vexnum; i++)
{
S[i] = 0;
D[i] = G.arcs[v0][i];
if (D[i] < MaxInt)
{
Path[i] = v0;
}
else
{
Path[i] = -1;
}
}
S[v0] = 1;
D[v0] = 0;
for (i = 1; i < G.vexnum; i++)
{
min = MaxInt;
for (j = 0; j < G.vexnum; j++)
{
if (!S[j] && D[j] < min)
{
v = j;
min = D[v];
}
}
S[v] = 1;
for (j = 0; j < G.vexnum; j++)
{
if (!S[j] && min + G.arcs[v][j] < D[j])
{
D[j] = min + G.arcs[v][j];
Path[j] = v;
}
}
}
//输出最短路径和最短距离
n = 0;
p[n] = G.vexs[v1];
for (k = v1; Path[k] >= 0; k = Path[k])
{
n++;
p[n] = G.vexs[Path[k]];
}
cout << "最短路径:" << p[n];
for (i = n - 1; i > 0; i--)
{
cout << "->" << p[i];
}
cout << "->" << p[i] << endl << "最短路径的距离:" << D[v1] << endl;
}