赞
踩
(1)两个顶点集 S 、T = V - S(V是原图所有顶点集合)
S:存放已找到最短路径的顶点
T:存放未找到最短路径的顶点
(2)实现步骤:
先将开始节点(V0)加入 S,不断从 T 中选取到 V0 有最短路径的顶点 (u),将 u 加入 S;S 中每加入一个顶点都要修改 V0 到 T 中剩余顶点的最短路径长度值。直到 T 中顶点全部加入 S。
终点 | V0 到各终点的 D 值和最短路径求解过程 | ||||
i = 1 | i = 2 | i = 3 | i = 4 | i = 5 | |
V1 | D[1] = p[1] = {0,0,0,0,0,0} | ||||
V2 | D[2] = 10 p[2] = {1,0,1,0,0,0} 即<V0,V2> | ||||
V3 | D[3] = p[3] = {0,0,0,0,0,0} | D[3] = 60 p[3] = {1,0,1,1,0,0} 即<V0,V2,V3> | D[3] = 50 p[3] = {1,0,0,1,1,0} 即<V0,V4,V3> | ||
V4 | D[4] = 30 p[4] = {1,0,0,0,1,0} 即<V0,V4> | D[4] = 30 p[4] = {1,0,0,0,1,0} 即<V0,V4> | |||
V5 | D[5] = 100 p[5] = {1,0,0,0,0,1} 即<V0,V5> | D[5] = 100 p[5] = {1,0,0,0,0,1} 即<V0,V5> | D[5] = 90 p[5] = {1,0,0,0,1,1} 即<V0,V4,V5> | D[5] = 60 p[5] = {1,0,0,1,1,1} 即<V0,V4,V3,V5> | |
Vj | V2 | V4 | V3 | V5 | |
S | {V0,V2} | {V0,V2,V4} | {V0,V2,V4,V3} | {V0,V2,V4,V3,V5} |
- package math_problem;
-
- import java.util.Arrays;
- import java.util.Scanner;
-
- class Graph {
- static final int MAX_VEX_NUM = 20; // 最大顶点数
- char[] vertex = new char[MAX_VEX_NUM]; // 顶点数组
- int graphType; // 图的类型。1-有向图,0-无向图
- int vexNum; // 实际顶点数
- int edgeNum; // 实际边数
- int[][] edgeWeight = new int[MAX_VEX_NUM][MAX_VEX_NUM]; // 保存边的权值
- }
-
- public class ShortestPathDemo {
- static Scanner input = new Scanner(System.in);
- static final int INFINITY = 65535; // 边上最大权值
-
- private static int getIndexOfChar(char[] charArray, char c) {
- for (int i = 0; i < charArray.length; i++) {
- if (c == charArray[i])
- return i;
- }
- return -1;
- }
-
- private void createGraph(Graph g) {
- int weight;
- char sVex, eVex;// 边的起始、结束顶点
-
- System.out.print("创建图,请输入图的类型(1:有向图/0:无向图):");
- g.graphType = input.nextInt();
-
- System.out.println("创建图,请输入各顶点信息...");
- System.out.print("请输入顶点数量:");
- g.vexNum = input.nextInt();
- for (int l = 0; l < g.vexNum; l++) {
- System.out.printf("第 %d 个顶点:", l+1);
- g.vertex[l] = (input.next().toCharArray())[0];
- }
-
- System.out.println("创建图,请输入各边顶点及权值...");
- System.out.print("请输入边数量:");
- g.edgeNum = input.nextInt();
-
- // 初始化邻接矩阵
- for (int i = 0; i < g.vexNum; i++) {
- for (int j = 0; j < g.vexNum; j++) {
- g.edgeWeight[i][j] = INFINITY;
- }
- }
-
- System.out.println("请依次输入每条边的信息(起始顶点,结束顶点,权值):");
- int indexOfsVex, indexOfeVex;
- for (int i = 0; i < g.edgeNum; i++) {
- sVex = input.next().charAt(0);
- eVex = input.next().charAt(0);
- weight = input.nextInt();
-
- indexOfsVex = getIndexOfChar(g.vertex, sVex);
- indexOfeVex = getIndexOfChar(g.vertex, eVex);
- g.edgeWeight[indexOfsVex][indexOfeVex] = weight;
- // 若是无向图,保存边 E(k,j)的权值
- if (g.graphType == 0) {
- g.edgeWeight[indexOfeVex][indexOfsVex] = weight;
- }
- }
- }
-
- // 输出邻接矩阵
- private void displayAdjMatrix(Graph g) {
- int i, j;
-
- // 先输出顶点信息
- for (i = 0; i < g.vexNum; i++) {
- System.out.printf("\t%c", g.vertex[i]);
- }
- System.out.println();
-
- // 输出邻接矩阵
- for (j = 0; j < g.vexNum; j++) {
- System.out.printf("%c", g.vertex[j]);
- for (i = 0; i < g.vexNum; i++) {
- if (g.edgeWeight[j][i] == INFINITY) {
- // 权值大于等于最大权值时,输出无穷大的符号
- System.out.print("\t∞");
- continue;
- }
- System.out.printf("\t%d", g.edgeWeight[j][i]);
- }
- System.out.println();
- }
- }
-
- private static void dijkstraShortestPath(Graph g) {
- int minWeight, indexOfsVex, k = 0;
- char startVex;
- int[] d = new int[g.vexNum];
- int[] s = new int[g.vexNum];
- int[][] p = new int[g.vexNum][g.vexNum];
-
- System.out.print("请输入开始节点:");
- startVex = input.next().charAt(0);
- indexOfsVex = getIndexOfChar(g.vertex, startVex);
-
- for (int i = 0; i < g.vexNum; i++) {
- d[i] = g.edgeWeight[indexOfsVex][i];
- if (d[i] < INFINITY) {
- p[i][indexOfsVex] = 1;
- p[i][i] = 1;
- }
- }
- // 将起始节点加入集合 S
- s[indexOfsVex] = 1;
-
- for (int i = 1; i < g.vexNum; i++) {
- minWeight = INFINITY;
- for (int j = 0; j < g.vexNum; j++) {
- if (s[j] != 1 && d[j] < minWeight) {
- minWeight = d[j];
- k = j;
- }
- }
- // 将新的节点加入集合 S
- s[k] = 1;
-
- for (int j = 0; j < g.vexNum; j++) {
- if (s[j] != 1 && (minWeight + g.edgeWeight[k][j] < d[j])) {
- d[j] = minWeight + g.edgeWeight[k][j];
- for (int l = 0; l < g.vexNum; l++) {
- p[j][l] = p[k][l];
- }
- p[j][j] = 1;
- }
- }
- }
-
- for (int i = 0; i < g.vexNum; i++) {
- for (int j = 0; j < g.vexNum; j++) {
- System.out.print(p[i][j] + " ");
- }
- System.out.println();
- }
-
- System.out.println(Arrays.toString(d));
- }
-
- public static void main(String[] args) {
- Graph graph = new Graph();
- ShortestPathDemo demo = new ShortestPathDemo();
- demo.createGraph(graph);
- demo.displayAdjMatrix(graph);
- demo.dijkstraShortestPath(graph);
- }
- }
- 创建图,请输入图的类型(1:有向图/0:无向图):1
- 创建图,请输入各顶点信息...
- 请输入顶点数量:6
- 第 1 个顶点:0
- 第 2 个顶点:1
- 第 3 个顶点:2
- 第 4 个顶点:3
- 第 5 个顶点:4
- 第 6 个顶点:5
- 创建图,请输入各边顶点及权值...
- 请输入边数量:8
- 请依次输入每条边的信息(起始顶点,结束顶点,权值):
- 0 2 10
- 0 4 30
- 0 5 100
- 4 5 60
- 4 3 20
- 3 5 10
- 2 3 50
- 1 2 5
- 0 1 2 3 4 5
- 0 ∞ ∞ 10 ∞ 30 100
- 1 ∞ ∞ 5 ∞ ∞ ∞
- 2 ∞ ∞ ∞ 50 ∞ ∞
- 3 ∞ ∞ ∞ ∞ ∞ 10
- 4 ∞ ∞ ∞ 20 ∞ 60
- 5 ∞ ∞ ∞ ∞ ∞ ∞
- 请输入开始节点:0
- 0 0 0 0 0 0
- 0 0 0 0 0 0
- 1 0 1 0 0 0
- 1 0 0 1 1 0
- 1 0 0 0 1 0
- 1 0 0 1 1 1
- [65535, 65535, 10, 50, 30, 60]
-
- Process finished with exit code 0
-
- #include <stdio.h>
- #include <stdlib.h>
-
- #define INFINITY 10000 /* 假定弧上权值无穷大时为10000 */
- #define MAX_VERTEX_NUM 100 /* 图中最大节点数 */
- typedef char VexType; /* 顶点类型设置为字符型 */
- typedef int weight; /* 弧上权值类型设置为整型 */
- typedef struct /* 弧表节点 */
- {
- VexType vex[MAX_VERTEX_NUM]; /* 图中节点 */
- weight edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM];/* 邻接矩阵 */
- int vexnum; /* 节点的数目 */
- int edgenum; /* 弧的数目 */
- }MGraph;
-
- void CreateDG(MGraph * DG); /* 邻接矩阵法创建有向图(directed graph) */
- void PrintDG(MGraph DG); /* 邻接矩阵形式输出图DG */
- void ShortestPath_Dijkstra(MGraph DG, VexType StartVex);
- /* 从节点StartVex开始求最短路径 */
- void locateVex(MGraph DG, VexType vex, int * index);
- /* 定位节点vex的下标并赋给index */
-
- int main(void)
- {
- MGraph g;
-
- CreateDG(&g);
- printf("------------------------------\n");
- printf("vexnum = %d ; edgenum = %d\n", g.vexnum, g.edgenum);
- printf("------------------------------\n");
- PrintDG(g);
- printf("------------------------------\n");
- ShortestPath_Dijkstra(g, '0');
-
- return 0;
- }
- void CreateDG(MGraph * DG)
- {
- int i = 0, j, k, w; /* w:权值 */
- char ch;
-
- printf("请依次输入顶点数、弧数:");
- scanf("%d %d", &(DG->vexnum), &(DG->edgenum));
-
- printf("请依次输入顶点(以回车结束输入):");
- getchar();
- while ((ch = getchar()) != '\n') /* 输入顶点信息 */
- DG->vex[i++] = ch;
-
- for (i = 0; i < DG->vexnum; i++) /* 初始化邻接矩阵 */
- for (j = 0; j < DG->vexnum; j++)
- DG->edges[i][j] = INFINITY;
-
- printf("顶点 | 下标\n");
- for (i = 0; i < DG->vexnum; i++) /* 显示图中顶点及其对应下标 */
- {
- printf("%3c%6d\n", DG->vex[i], i);
- }
-
- printf("请输入依次每条弧的弧尾下标(不带箭头)、弧头下标(带箭头)、权值(格式:i j w):\n");
- for (k = 0; k < DG->edgenum; k++) /* 建立邻接矩阵 */
- {
- scanf("\n%d%d%d", &i, &j, &w); /* 输入弧的两个节点及权值 */
- DG->edges[i][j] = w; /* 将矩阵对应位置元素置为权值 */
- }
- }
- void PrintDG(MGraph DG)
- {
- int i, j;
-
- for (i = 0; i < DG.vexnum; i++) /* 输出邻接矩阵 */
- {
- for (j = 0; j < DG.vexnum; j++)
- {
- if (DG.edges[i][j] == INFINITY) /* 节点不连通时,输出无穷大 */
- printf(" ∞");
- else /* 节点连通时,输出弧上权值 */
- printf("%5d", DG.edges[i][j]);
- }
- printf("\n");
- }
- }
- void ShortestPath_Dijkstra(MGraph DG, VexType StartVex)
- {
- int i, j, v, index; /* index:开始节点下标 */
- int min; /* 开始节点到指定节点的最短路径权值和 */
- int final[DG.vexnum]; /* 集合S,元素值为1:下标为i的节点以加入集合S;为0:未加入 */
- int P[DG.vexnum][DG.vexnum];/* 开始节点到各节点的最短路径 */
- int D[DG.vexnum]; /* 开始节点到下标为i的节点的最短路径权值之和 */
-
- locateVex(DG, StartVex, &index);
- for (i = 0; i < DG.vexnum; i++)
- {
- final[i] = 0; /* 初始化,刚开始集合S为空 */
- D[i] = DG.edges[index][i];
-
- for (j = 0; j < DG.vexnum; j++) /* 初始化路径,假设所有节点都不连通 */
- P[i][j] = 0;
- if (D[i] < INFINITY) /* 若节点连通,则在数组P[i]中标明路径 */
- {
- P[i][index] = 1;
- P[i][i] = 1;
- }
- }
- D[index] = 0; final[index] = 1; /* 开始节点加入S集 */
-
- for (i = 1; i < DG.vexnum; i++)
- {
- min = INFINITY;
- for (j = 0; j < DG.vexnum; j++)
- if (!final[j])
- if (D[j] < min) { v = j; min = D[j]; }
- final[v] = 1; /* 把离StartVex最近的下标为v的节点加入S */
-
- for (j = 0; j < DG.vexnum; j++)
- if (!final[j] && (min + DG.edges[v][j] < D[j]))
- {/* 若下标为j的节点为加入S且有更短路径,则更新D[j]和最短路径 */
- D[j] = min + DG.edges[v][j];
- for (int k = 0; k < DG.vexnum; k++)
- P[j][k] = P[v][k];
- P[j][j] = 1;
- }
- }
-
- printf("节点 %c 到各节点的最短路径:\n", StartVex);
- for (i = 0; i < DG.vexnum; i++)
- {
- for (j = 0; j < DG.vexnum; j++)
- printf("%5d", P[i][j]);
- printf("\n");
- }
-
- printf("节点 %c 到各节点的最短路径值:", StartVex);
- for (i = 0; i < DG.vexnum; i++)
- {
- if (D[i] == INFINITY)
- printf("∞, ");
- else
- printf("%d, ", D[i]);
- }
- }
- void locateVex(MGraph DG, VexType vex, int * index)
- {
- int i;
-
- for (i = 0; i < DG.vexnum; i++)
- {
- if (DG.vex[i] == vex)
- {
- *index = i;
- return;
- }
- }
- printf("节点定位失败!\n");
- }
-
-
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。