Discussion :

[Tems2008]

Bonjour,

Je développe en vb.net et travaille actuellement sur l'algorithme de Dijkstra.
J'ai trouvé du code que je convertirai plus tard. Le but étant de bien comprendre et d'appliquer l'existant.

Mon objectif, comme vous l'aurez deviné, est de calculer des itinéraires à partir d'une carte bitmap. Il me faut donc disposer des sommets et des liaisons pour la mise en oeuvre.

J'ai les rues et leurs coordonnées. Ce que je n'arrive pas à comprendre, c'est comment réaliser le fichier XML (de l'exemple) avec les sommets et les liaisons pour chacune des rues. Bref, comment calculer les liaisons à partir de tous les sommets ?

Le suppose qu'il existe une solution logicielle, mais ne la connais pas et ne suis pas tombé sur des résultats probants via google.

Si quelqu'un a déjà travaillé dessus, je serais heureux de disposer de plus d'informations.

Merci d'avance

Tems 2008

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
    <Project DefaultTargets="Build" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
    <PropertyGroup>
    <Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration>
    <Platform Condition=" '$(Platform)' == '' ">AnyCPU</Platform>
    <ProductVersion>8.0.50727</ProductVersion>
    <SchemaVersion>2.0</SchemaVersion>
    <ProjectGuid>{D3881FA4-B07D-4325-B0AF-F675D5148DCB}</ProjectGuid>
    <OutputType>WinExe</OutputType>
    <AppDesignerFolder>Properties</AppDesignerFolder>
    <RootNamespace>Dijkstra</RootNamespace>
    <AssemblyName>Dijkstra</AssemblyName>
    <StartupObject>Dijkstra.Program</StartupObject>
    <ApplicationIcon>52.ico</ApplicationIcon>
    </PropertyGroup>
    <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' ">
    <DebugSymbols>true</DebugSymbols>
    <DebugType>full</DebugType>
    <Optimize>false</Optimize>
    <OutputPath>bin\Debug\</OutputPath>
    <DefineConstants>DEBUG;TRACE</DefineConstants>
    <ErrorReport>prompt</ErrorReport>
    <WarningLevel>4</WarningLevel>
    <DocumentationFile>
    </DocumentationFile>
    </PropertyGroup>
    <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' ">
    <DebugType>pdbonly</DebugType>
    <Optimize>true</Optimize>
    <OutputPath>bin\Release\</OutputPath>
    <DefineConstants>TRACE</DefineConstants>
    <ErrorReport>prompt</ErrorReport>
    <WarningLevel>4</WarningLevel>
    <DocumentationFile>
    </DocumentationFile>
    </PropertyGroup>
    <ItemGroup>
    <Reference Include="System" />
    <Reference Include="System.Data" />
    <Reference Include="System.Deployment" />
    <Reference Include="System.Drawing" />
    <Reference Include="System.Runtime.Serialization.Formatters.Soap" />
    <Reference Include="System.Windows.Forms" />
    <Reference Include="System.Xml" />
    </ItemGroup>
    <ItemGroup>
    <Compile Include="Apropos.cs">
    <SubType>Form</SubType>
    </Compile>
    <Compile Include="AlgoDijkstra.cs" />
    <Compile Include="Carte.cs">
    <SubType>Form</SubType>
    </Compile>
    <Compile Include="Carte.Designer.cs">
    <DependentUpon>Carte.cs</DependentUpon>
    </Compile>
    <Compile Include="Liaison.cs" />
    <Compile Include="map.cs" />
    <Compile Include="Program.cs" />
    <Compile Include="Properties\AssemblyInfo.cs" />
    <EmbeddedResource Include="Apropos.resx">
    <DependentUpon>Apropos.cs</DependentUpon>
    <SubType>Designer</SubType>
    </EmbeddedResource>
    <EmbeddedResource Include="Carte.resx">
    <SubType>Designer</SubType>
    <DependentUpon>Carte.cs</DependentUpon>
    </EmbeddedResource>
    <EmbeddedResource Include="Properties\Resources.resx">
    <Generator>ResXFileCodeGenerator</Generator>
    <LastGenOutput>Resources.Designer.cs</LastGenOutput>
    <SubType>Designer</SubType>
    </EmbeddedResource>
    <Compile Include="Properties\Resources.Designer.cs">
    <AutoGen>True</AutoGen>
    <DependentUpon>Resources.resx</DependentUpon>
    <DesignTime>True</DesignTime>
    </Compile>
    <None Include="Properties\Settings.settings">
    <Generator>SettingsSingleFileGenerator</Generator>
    <LastGenOutput>Settings.Designer.cs</LastGenOutput>
    </None>
    <Compile Include="Properties\Settings.Designer.cs">
    <AutoGen>True</AutoGen>
    <DependentUpon>Settings.settings</DependentUpon>
    <DesignTimeSharedInput>True</DesignTimeSharedInput>
    </Compile>
    <Compile Include="Sommet.cs" />
    </ItemGroup>
    <ItemGroup>
    <Content Include="52.ico" />
    </ItemGroup>
    <ItemGroup>
    <Folder Include="Resources\" />
    </ItemGroup>
    <Import Project="$(MSBuildBinPath)\Microsoft.CSharp.targets" />
    <!-- To modify your build process, add your task inside one of the targets below and uncomment it.
    Other similar extension points exist, see Microsoft.Common.targets.
    <Target Name="BeforeBuild">
    </Target>
    <Target Name="AfterBuild">
    </Target>
    -->
    </Project>

[LinuxUser]

Qu'est ce que tu appelles liaison?
Pour moi ce qui lie deux sommets, c'est une arête.

[Tems2008]

Le sommet est représenté par un point, par exemple une ville à laquelle sont associées ses coordonnées.

La liaison est la relation entre 2 ou plusieurs points. Chaque liaison ayant un cout, par exemple la distance, ce qui permettra à l'algorithme de trouver le chemin le plus court, le plus rapide, etc.

[Tems2008]

Finalement, j'ai compris le principe. C'était simple