狄杰斯特拉最短路径算法实现

狄杰斯特拉最短路径算法实现，地图用二维数组刻画

import java.util.ArrayList;
import java.util.linkedList;
import java.util.Scanner;

public class Shortest_path {

	public static class Node
	{
		int number = -1;		  //�ڵ���
		int weight = maxweight;   //��ʼ�ڵ㵽���ڽڵ��������С����
		int fore = -1;    //��¼ʹ����ʼ�ڵ���뵱ǰ�ڵ�·����̵ĵ�ǰ�ڵ��ǰ��
	}
	
	public static final  int maxweight = 1024;
	//public static int[][] graph = new int[][]{{031-1}{30-11}{1-102}{-1120}};
	public static int[][] graph = new int[][]{
		{022-1-1-1-1-1-1}
		{20-16-17-1-1}
		{2-101-1-14-1}
		{-16102-1-1-1}
		{-1-1-12032-1}
		{-17-1-130-13}
		{-1-14-12-102}
		{-1-1-1-1-1320}};
	/*public static int[][] graph = new int[][]{
		{053-1-1-1-1-1-1}
		{50-1136-1-1-1}
		{3-10-187-1-1-1}
		{-11-10-1-13-1-1}
		{-138-10-152-1}
		{-167-1-1026-1}
		{-1-1-13560-14}
		{-1-1-1-126-103}
		{-1-1-1-1-1-1430}};  */
	public static ArrayList listnode = new ArrayList（）;
	public static linkedList intlist = new linkedList（）; //��ǰδ����ڵ�
	public static linkedList templist = new linkedList（）; //��Ҫ����Ľڵ�Ķ���
	public static int[] path = new int[graph.length];
	public static void main（String[] args） {
		
		Scanner s = new Scanner（System.in）;
		System.out.println（“�����뿪ʼ�ڵ��Ŀ��ڵ�（�м��ÿո����）:“）;
		int start = s.nextInt（）;
		int target = s.nextInt（）;
		s.close（）;
		
		initialize（starttarget）;
		if（is_exist（start target））
		{
			graph_printer（graph）;
			shortest_path（ start target）;
		}
		else
		{
			System.err.println（“������Ľڵ㲻���ڣ�“）;
		}
		
	}

	//��ʼ��ÿ���ڵ㣬�������������
	public static void initialize（int start int target）
	{
		for（int i=1 ; i<=graph.length ; i++）
		{
			intlist.add（i）;
			path[i-1] = 0;
			Node node = new Node（）;
			node.number = i ;
			if（i == start）
			{
				node.weight = 0;
			}
			listnode.add（node）;
		}
	}
	
	//��ӡ��ͼ�Ĺ���
	public static void graph_printer（int[][] graph）
	{
		System.out.println（“ͼ�ĽṹΪ:“）;
		for（int i=0; i		{
			for（int j=0; j			{
				System.out.printf（“%3d“graph[i][j]）;
			}
			System.out.println（““）;
		}
		System.out.println（““）;
	}

	//�������Ľڵ��Ƿ����
	public static boolean is_exist（int start  int target）
	{
		boolean exsit1 = false;
			if（start > 0 && start <= graph.length && target > 0 && target <= graph.length）
			{
				 exsit1 =true;
			}
		return exsit1;
	}
	//���·���㷨���Ͻ�˹�����㷨��
	public static void shortest_path（int start  int target）
	{
		System.out.print（“��ʼ�ڵ�:“+start）;
		do{
			for（int i=0; i			{
				if（graph[i][start-1] > 0）    //˵���õ�����ʼ�ڵ����ھ�
				{
					if（graph[i][start-1]+listnode.get（start-1）.weight < listnode.get（i）.weight）
					{
						listnode.get（i）.weight = graph[i][start-1]+listnode.get（start-1）.weight;

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件        301  2013-11-23 18:40  .classpath

     文件        389  2013-11-23 18:40  .project

     文件        598  2013-11-23 18:40  .settings\org.eclipse.jdt.core.prefs

     文件        447  2014-10-20 22:43  bin\Shortest_path$Node.class

     文件       4518  2014-10-20 22:43  bin\Shortest_path.class

     文件       4742  2014-10-20 22:43  src\Shortest_path.java

     目录          0  2014-03-12 21:54  .settings

     目录          0  2014-10-20 22:40  bin

     目录          0  2014-03-12 21:54  src

----------- ---------  ---------- -----  ----

                10995                    9