描述：
Dijstra算法代码基本与Prim算法相同，不过需要打印出路径和路径长度，所以需要稍作修改，修改的地方都已注释标出
顶点：
class Vertex
{
public int data;
public Vertex(int data)
{
this.data = data;
}
}
边：
class Edge
{
public int tail;
public int head;
public int width;
public Edge(int tail, int head, int width)
{
this.tail = tail;
this.head = head;
this.width = width;
}
}
构造邻接矩阵：
class DijkstraShortestPath
{
int[,] matrix;
int vexCount;
public void GraphAdjacencyMatrix(Vertex[] vex, Edge[] edge)
{
matrix = new int[vex.Length, vex.Length];
for (int i = 0; i < vex.Length; i++)
{
for (int j = 0; j < vex.Length; j++)
{
if (i != j)
{
matrix[i, j] = 1000;
}
}
}
vexCount = vex.Length;
for (int i = 0; i < edge.Length; i++)
{
int tail = edge[i].tail;
int head = edge[i].head;
matrix[tail, head] = edge[i].width;
matrix[head, tail] = edge[i].width;
}
Console.WriteLine("邻接矩阵：");
Console.Write("\t ");
for (int i = 0; i < vex.Length; i++)
{
Console.Write(vex[i].data + "\t ");
}
Console.WriteLine("\n\n");
for (int i = 0; i < vex.Length; i++)
{
Console.Write(vex[i].data + "\t");
for (int j = 0; j < vex.Length; j++)
{
Console.Write("[" + matrix[i, j] + "]\t");
}
Console.WriteLine("\n\n");
}
}
Dijkstra算法：
public void Dijkstra(int source)
{
int[] minVex = new int[vexCount];
int[] minWidth = new int[vexCount];
int[] minCost = new int[vexCount];//这个数组是用来记录起点到某点（索引对应的点）的最短路径长度的
for (int i = 0; i < vexCount; i++)
{
minVex[i] = source;
minWidth[i] = matrix[source, i];
minCost[i] = matrix[source, i];//记录起点到某点的最短路径长度
}
Console.WriteLine("顶点" + source + "到各顶点的最短路径是：");
for (int i = 0; i < vexCount - 1; i++)
{
int min = 1000;
int k = source;
for (int j = 0; j < vexCount; j++)
{
if (minWidth[j] != 0 && minWidth[j] < min)
{
min = minWidth[j];
k = j;
}
}
minWidth[k] = 0;
for (int j = 0; j < vexCount; j++)
{
if (minWidth[j] != 0 && matrix[k,j] < minWidth[j])
{
minWidth[j] = matrix[k, j];
minCost[j] = minCost[k] + matrix[k, j];//这句用来修改加入新顶点后，起点到某点的最短路径长度变得更短后的路径值
minVex[j] = k;
}
}
}
//这段是打印，因为顶点数组中存放的是到其索引顶点最近的点，所以可以反向导出指定点到其余各点的路径
for (int j = 0; j < vexCount; j++)
{
if (j != source)
{
int next = j;
Console.Write("最短路径长度是：" + minCost[j] + "\t" + j + " <- ");
while (minVex[next] != source)
{
Console.Write(minVex[next] + " <- ");
next = minVex[next];
}
Console.Write(source + "\n");
}
}
}
}
}
以下图为例求顶点2到其余各点的最短路径：
图
Main函数：
DijkstraShortestPath dijkstra = new DijkstraShortestPath();
Vertex vex0 = new Vertex(0);
Vertex vex1 = new Vertex(1);
Vertex vex2 = new Vertex(2);
Vertex vex3 = new Vertex(3);
Vertex vex4 = new Vertex(4);
Vertex vex5 = new Vertex(5);
Vertex vex6 = new Vertex(6);
Vertex vex7 = new Vertex(7);
Vertex vex8 = new Vertex(8);
Vertex[] vex = { vex0, vex1, vex2, vex3, vex4, vex5, vex6, vex7, vex8 };
Edge edge0 = new Edge(0, 1, 1);
Edge edge1 = new Edge(0, 2, 5);
Edge edge2 = new Edge(1, 2, 3);
Edge edge3 = new Edge(1, 3, 7);
Edge edge4 = new Edge(1, 4, 5);
Edge edge5 = new Edge(2, 4, 1);
Edge edge6 = new Edge(2, 5, 7);
Edge edge7 = new Edge(3, 4, 2);
Edge edge8 = new Edge(3, 6, 3);
Edge edge9 = new Edge(4, 5, 3);
Edge edge10 = new Edge(4, 6, 6);
Edge edge11 = new Edge(4, 7, 9);
Edge edge12 = new Edge(5, 7, 5);
Edge edge13 = new Edge(6, 7, 2);
Edge edge14 = new Edge(6, 8, 7);
Edge edge15 = new Edge(7, 8, 4);
Edge[] edge = { edge0, edge1, edge2, edge3, edge4, edge5, edge6, edge7, edge8, edge9, edge10, edge11, edge12, edge13, edge14, edge15 };
dijkstra.GraphAdjacencyMatrix(vex, edge);
dijkstra.Dijkstra(2);
运行结果如下：
运行结果
